Does submodular mean that adding an item always helps?

No. That is monotonicity. Submodularity governs how marginal changes compare as the selected set grows.

Is ordinary coverage submodular?

Yes, when value counts the union of covered elements, with nonnegative fixed weights if weighted coverage is used.

Does the 63.2 percent guarantee predict typical business results?

No. It is a worst-case mathematical bound under specific assumptions, not a forecast of practical value.

AI Glossary / Computer vision and multimodal AI / Intermediate

Submodularity

Definition

Submodularity is a mathematical property of a set function that expresses diminishing marginal returns. Adding an item to a smaller selected set provides at least as much additional value as adding the same item to a larger set containing it. This property helps describe selection problems where candidates overlap in the benefits they provide.

What it means

A set function assigns a number to a collection of items. The items might be photographs, sensors, documents, or candidate training examples. Its value could measure coverage, diversity, or another carefully defined objective.

Submodularity concerns how the value changes as the collection grows. A photograph showing a previously unseen view may add considerable coverage. The same photograph may add little after several similar views have already been selected.

Submodularity and monotonicity are different properties. Monotonicity means that adding items never reduces the function value. A function can be submodular without being monotone. The distinction matters because algorithms and guarantees depend on the exact combination of properties and constraints, not merely an informal impression of diminishing usefulness.

How it works

Let A be a subset of B, and let item x belong to neither selected set. Submodularity requires:

f(A ∪ {x}) − f(A) ≥ f(B ∪ {x}) − f(B).

The differences are marginal gains. An equivalent set-function condition is f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B).

A common selection approach repeatedly adds the item with the largest current marginal gain. For maximizing a normalized, nonnegative, monotone submodular function under a cardinality limit, the standard greedy algorithm has a worst-case guarantee of at least 1 − 1/e, approximately 63.2 percent of the optimal value. This is not a universal guarantee for arbitrary budgets, nonmonotone functions, or other constraints. The objective must actually satisfy the relevant assumptions.

Three practical examples

1. A video summary selects frames to cover different visual situations. A coverage objective can give less additional value to frames that repeat already represented content, reducing redundancy in the selected set.

2. A sensor planning exercise values the number of locations observed by at least one chosen sensor. Overlapping fields of view create diminishing coverage gains, although reliability and other requirements may need additional modeling.

3. A document collection chooses examples covering a set of topics. Counting each covered topic once produces a straightforward coverage objective. It does not by itself ensure balanced representation or the quality of the selected documents.

Think of it this way

Think of collecting maps that cover different parts of a region. The first map may add many new places; a later map mostly overlapping the collection adds fewer. The analogy explains coverage-based diminishing returns. It is limited because some real items are complements: two pieces of equipment may be useful only together, which can violate this property.

Worked example

Suppose three candidate images cover labeled features:

P covers {door, window, roof}.
Q covers {window, roof, chimney}.
R covers {garden, gate}.

Define f(S) as the number of distinct features covered by images in S. The empty collection has value zero.

Adding Q to the empty collection gains three features. Adding Q after P gains only chimney, so the marginal gain is one. This is a concrete diminishing-returns comparison.

With a two-image limit, suppose greedy selection breaks the initial tie between P and Q by choosing P. The next marginal gains are one for Q and two for R. It chooses R, giving five covered features. Selecting P and Q would cover four.

Now consider a different objective that awards ten points only when both P and Q are selected. Q adds zero to the empty set but ten after P. That complementary reward violates diminishing returns. Calling a selection problem submodular therefore depends on the function, not on the fact that it involves choosing images.

Illustrative case study

Fictional case study: SceneShelf builds small image collections for reviewing warehouse layouts. Its first selection rule chooses individually popular images, producing many near-duplicate views of the loading area.

The team defines a feature-coverage objective and recalculates each candidate's gain after every selection. It reviews the resulting sets with staff who know the building. They discover that a rarely photographed emergency exit deserves explicit inclusion even though it contributes few of the original feature labels.

The team revises its selection specification rather than assuming the mathematical objective captured every operational need. This fictional case illustrates the difference between optimizing a function and choosing the right function; it does not report measured safety or productivity outcomes.

Common misconceptions and mistakes

Do not equate submodularity with an exact greedy solution. The standard guarantee bounds performance under specified assumptions; it does not promise that every greedy result is optimal.

Do not infer submodularity from a few examples. The defining inequality must hold across the relevant sets and added items, or be established analytically for the chosen function.

Also distinguish diversity from usefulness. An objective can reward broad coverage while selecting inaccurate, low-quality, or irrelevant material unless those concerns are represented or checked separately.

Business use

Submodular objectives can make large selection tasks more manageable and explainable. A team can inspect why an item was chosen by examining the additional coverage or other value it supplied at that step.

Document the function, constraints, tie-breaking rule, and computational assumptions. Compare the output with simple baselines and, on small cases, an exact search. When requirements change from an item-count limit to unequal costs or mandatory groups, reassess the algorithm and guarantee rather than carrying over an approximation claim unchanged.

Check your understanding

An item adds nothing alone but becomes very valuable after another item is selected. Does that interaction necessarily satisfy diminishing returns?

Answer: No. The larger marginal gain after the set grows can violate submodularity, as with complementary items that only work together.

Related terms

Greedy algorithms
Monotonicity
Set function
marginal gain
greedy algorithm
maximum coverage
approximation algorithm

Learn next

Start with coverage functions on small sets and calculate marginal gains after each choice. Then study greedy approximation guarantees, paying attention to normalization, monotonicity, and the precise selection constraint.

Monotonicity

Sources

Tim Roughgarden, CS261 Problem Set 4, Problem 20, submodular maximization and greedy approximation: https://timroughgarden.org/w16/ps/ps4.pdf

The instructor's material supports the defining property and guarantee. The image-feature sets and fictional selection workflow are original illustrations.

Previous: Submodular optimization Next: Subproblem