Non-Monotone Submodular Optimization

161 concepts141 papers1 proposal

In discrete optimization, the concept of submodularity formalizes the intuitive law of diminishing returns: adding an item to a smaller collection yields a larger or equal marginal benefit than adding that same item to a larger collection. Mathematically, a set function $f: 2^V \to \mathbb{R}$ is submodular if for all subsets $A \subseteq B \subseteq V$ and any element $x \notin B$:

$$f(A \cup \{x\}) - f(A) \ge f(B \cup \{x\}) - f(B)$$

For decades, the gold standard for maximizing these functions has relied on an additional assumption: monotonicity. A function is monotone if adding an element never decreases its total value ($f(A \cup \{x\}) \ge f(A)$). When a function is both monotone and submodular, a simple greedy algorithm—consistently picking the element with the highest immediate marginal gain—guarantees a solution within a factor of $(1 - 1/e) \approx 63\%$ of the global optimum.

However, many real-world problems break this assumption. Consider feature selection in machine learning, document summarization, or mutual information maximization. In these settings, adding too many items introduces noise, redundancy, or overhead that causes the overall utility to drop. As noted by Kai Wei et al. in Fast Multi-stage Submodular Maximization, vital metrics like mutual information are inherently non-monotone. When monotonicity is lost, standard optimization toolkits shatter, forcing researchers to design algorithms that can safely navigate landscapes where marginal gains can be negative.

Why Naive Greed Fails

To understand why non-monotonicity paralyzes the standard greedy approach, imagine climbing a hill in a dense fog. If the terrain is monotone, every step upward increases your absolute altitude; you might get stuck on a sub-optimal peak, but you will never accidentally walk off a cliff into a valley lower than where you started.

In a non-monotone landscape, the terrain slopes downward past a certain point. A naive greedy algorithm evaluates choices purely on immediate marginal gains. It can easily be blinded by an item that offers a massive initial boost but subsequently forces all future choices to have deeply negative marginal returns.

As highlighted by Grigory Yaroslavtsev in "Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack, standard greedy selection can aggressively over-select items, overshooting the optimal peak of the function and destroying the utility of the chosen subset. Because the algorithm cannot backtrack, it traps itself in a sub-optimal valley.

Continuous Relaxations and Smooth Navigation

One of the most elegant solutions to this problem bypasses discrete choices entirely by smoothing the bumpy, discrete landscape into a continuous space. This is achieved via the multilinear extension $F: [0, 1]^V \to \mathbb{R}$. Instead of deciding whether an item is strictly in ($1$) or out ($0$) of a set, we assign each item a fractional probability $x_i \in [0, 1]$. The continuous function $F(x)$ represents the expected value of the discrete function $f$ if subsets are sampled according to those probabilities.

Once the problem is continuous, we can leverage gradient-like steps to find the optimum. For monotone functions, the classic Continuous Greedy algorithm moves along directions of positive growth. For non-monotone functions, however, the true gradient can point toward regions that ultimately reduce the objective value.

Discrete Space {0, 1}^V  --->  Continuous Space [0, 1]^V  --->  Gradient Ascent / Rounding
(Bumpy, sharp drops)            (Smoothed expectations)          (Safe navigation past peaks)

To safely navigate this continuous space, An Bian et al. developed a principled framework in Non-monotone Continuous DR-submodular Maximization: Structure and Algorithms. They demonstrated that by enforcing down-closed convex constraints, algorithms can bound how fast they move through regions of negative marginal growth.

By controlling the step sizes, the continuous trajectory avoids over-committing to directions that suffer from severe downward slopes. Once a fractional solution is found, specialized rounding techniques collapse the probabilities back into a discrete set without losing the approximation guarantees. Expanding on this, Mehrdad Ghadiri et al. showed in Beyond Submodular Maximization via One-Sided Smoothness that this continuous-to-discrete pipeline can be generalized to even broader non-submodular domains by leveraging one-sided smoothness properties to control the approximation error during the rounding phase.

Guardrails via Distorted Objectives

If continuous relaxation is too computationally expensive, how do we fix the discrete greedy algorithm? The answer lies in changing what the algorithm "sees." If an algorithm is prone to over-selecting because it is blind to future drops, we can introduce a mathematical guardrail that penalizes early greed.

This mechanism is beautifully illustrated in the context of maximizing a submodular utility minus a linear cost—a combination that frequently yields negative overall values. In Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications, Christopher Harshaw et al. introduced the Distorted Greedy algorithm.

Instead of evaluating an item $x$ based on its true marginal gain $\Delta f(x \mid A)$, the algorithm scales the gain using a time-varying factor that depends on how much of the budget has been spent. Early on, the algorithm heavily discounts marginal gains. This distortion acts as a dynamic brake: it prevents the algorithm from burning through its budget on items that look spectacular in isolation but cause massive negative externalities later, ensuring a tight approximation ratio even when the total objective can drop below zero.

Robustness and Constraints in Flight

In practical applications, non-monotone optimization must operate under real-world constraints—such as knapsack (budget) limitations—and must remain resilient to adversarial data loss or streaming memory bounds.

When an adversary can delete elements from your selected subset, non-monotonicity introduces severe volatility. In a monotone setting, losing an item simply drops your score by that item's marginal contribution. In a non-monotone setting, losing an item can unpredictably alter the interactions of the remaining elements.

As explored by Dmitrii Avdiukhin et al. in Adversarially Robust Submodular Maximization under Knapsack Constraints, robust algorithms cannot rely on a single, brittle greedy path. Instead, they must maintain a broader "robust summary" of elements to ensure that if an adversary deletes the top items, the remaining elements still interact favorably.

Translating these guardrails into streaming environments—where data arrives sequentially and cannot be re-examined—presents a parallel challenge. While researchers like Alina Ene et al. have established efficient streaming frameworks for multi-category selection in Streaming Algorithm for Monotone k-Submodular Maximization with Cardinality Constraints, adapting these single-pass memory buffers to handle the unpredictable downward slopes of fully non-monotone objectives remains one of the most active and vital frontiers in discrete optimization.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 139 papers
  2. Version 1 · 2026-10-04 · 178 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_non_monotone_submodular_optimization_91061038,
  title = {non-monotone submodular optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-monotone-submodular-optimization/rdr_91061038619f41839fa2b17caa79b297},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_non_monotone_submodular_optimization_91061038_v2,
  title = {non-monotone submodular optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-monotone-submodular-optimization/rdr_91061038619f41839fa2b17caa79b297/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake