Stochastic Greedy Selection for Non-Monotone Optimization

77 concepts60 papers2 proposals

The classic greedy algorithm is simple: start with an empty set, scan your options, and repeatedly pick the single element that provides the highest immediate marginal gain. For monotone submodular functions—where adding elements always increases or maintains the total value, even if returns diminish over time—this myopic strategy works remarkably well.

However, real-world optimization problems are rarely perfectly monotone. In tasks like data summarization, feature selection, or viral marketing, adding too many elements can introduce redundancy, noise, or penalties, causing the overall objective value to drop. In these non-monotone landscapes, pure greed fails catastrophically. It eagerly grabs high-value items early on, which then "blind" the algorithm, trapping it in local optima or prematurely exhausting budgets before more robust combinations can be discovered.

To overcome this limitation, a powerful paradigm has emerged: stochastic greedy selection. By strategically injecting randomness into the selection process, these algorithms transform a short-sighted heuristic into a robust optimization strategy with strong theoretical guarantees.

Mechanism 1: Pre-Filtering and Subsampling

One of the most elegant ways to break the greedy trap is to hide data from the algorithm before it even begins. If a greedy algorithm is prone to making bad, short-sighted commitments based on early high-value items, we can mitigate this by randomly restricting its choices.

In Greed Is Good: Near-Optimal Submodular Maximization via Greedy Optimization., Moran Feldman et al. demonstrate that randomly filtering a dataset before applying a greedy selection process prevents the algorithm from selecting elements that look locally optimal but negatively impact the global non-monotone objective. This acts as a safeguard against redundancy penalties.

Similarly, Federico Fusco et al. in Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint utilize a pre-selection randomization step that independently discards items with a fixed probability. This mechanism forces the exploration of more robust solution sets, ensuring the algorithm isn't derailed by a few deceptive, high-gain elements.

In streaming environments where data arrives sequentially, this concept evolves into stochastic filtering. As shown by Moran Feldman et al. in Do Less, Get More: Streaming Submodular Maximization with Subsampling, randomly ignoring elements in a stream acts as a regularization technique. It prevents the algorithm's solution set from becoming prematurely saturated with mediocre early arrivals, which is vital when later items might yield a higher total utility.

Mechanism 2: Selecting from a Candidate Pool

Instead of filtering the input data beforehand, a second approach alters the choice step itself. Rather than deterministically picking the absolute best element, the algorithm identifies a pool of top-performing candidates and samples from them.

Alkis Gotovos et al. in Non-Monotone Adaptive Submodular Maximization propose selecting uniformly at random from a set of top candidates rather than always choosing the single best option. This simple injection of stochasticity acts as a safety net against short-sighted decisions that would otherwise lead to utility traps.

This pool-based strategy is exceptionally robust, providing mathematical safety nets even when the objective function is highly irregular. For instance, Chao Qian et al. in Approximation Guarantees of Stochastic Greedy Algorithms for Subset Selection and Lin Chen et al. in Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy? demonstrate that selecting uniformly at random from a set of high-performing marginal candidates provides provable approximation guarantees for functions that are non-submodular or only weakly submodular. The randomness prevents the search process from falling into local optima caused by the lack of strict diminishing returns.

Mechanism 3: Randomized Thresholds and Fractional Gains

A third facet of this direction involves dynamically adjusting selection thresholds or scaling selection probabilities based on an item's relative value.

Shinsaku Sakaue in Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint shows that a stochastic greedy algorithm that randomly omits certain high-gain elements can bypass deceptive local optima in linear time. Rather than uniform pool selection, algorithms can also choose elements with a probability directly proportional to their estimated marginal contributions, as explored by Lan N. Nguyen et al. in Streaming k-Submodular Maximization under Noise subject to Size Constraint. This prevents the algorithm from being overly sensitive to local noise spikes or suboptimal early arrivals.

Furthermore, Avinatan Hassidim et al. in Robust Guarantees of Stochastic Greedy Algorithms analyze mechanisms where an element is selected if its marginal contribution is a random fraction of the maximum available gain. This allows for massive computational efficiency and noise tolerance while maintaining predictable performance over multiple sequential selection steps.

Why It Works: Smoothing the Landscape in Expectation

Why does adding randomness improve worst-case guarantees for deterministic optimization problems? The core intuition lies in how randomization smooths out a non-monotone landscape in expectation.

In a non-monotone setting, a deterministic greedy choice is fragile because it optimizes purely for the immediate step. If the absolute best immediate item happens to conflict with future high-value items, the deterministic algorithm is trapped. By forcing the algorithm to flip a coin—whether by subsampling the input, choosing from a candidate pool, or using randomized thresholds—the algorithm avoids over-committing to any single myopic path.

As Roie Levin et al. demonstrate in Streaming Submodular Matching Meets the Primal-Dual Method, discarding valid candidates with a fixed probability ensures that dual constraints are satisfied in expectation. This prevents early selections from disproportionately exhausting the budget. By optimizing for the expected outcome rather than the immediate maximum, stochastic greedy selection transforms a fragile, easily tricked heuristic into a robust, globally aware optimization strategy.

Key Foundational Work

Probabilistic constructive optimization techniques (2004) — contributed 1 concept elements to this direction.
Fast Training of Support Vector Classifiers (2000) — 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_randomized_greedy_selection_stochastic_g_4d44a5f8,
  title = {randomized greedy selection (stochastic greedy optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-greedy-selection-stochastic-greedy-optimization/rdr_4d44a5f8de4046f090e10848b698b0fb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_randomized_greedy_selection_stochastic_g_4d44a5f8_v1,
  title = {randomized greedy selection (stochastic greedy optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/randomized-greedy-selection-stochastic-greedy-optimization/rdr_4d44a5f8de4046f090e10848b698b0fb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake