Submodularity: The Mathematics of Diminishing Returns

Suppose you are placing sensors to monitor a river, and each sensor covers some stretch. The first sensor you place is enormously valuable; it covers ground nothing else did. The tenth adds less, because much of what it sees is already watched by the first nine. The hundredth barely helps.

That pattern, where each additional item contributes less than the one before, is diminishing returns, and it is everywhere. An extra advertisement reaches fewer new people once most have seen your others. An extra training example teaches less once similar ones are in the set. An extra word in a summary adds less once the main points are covered.

Submodularity is the exact mathematical statement of this intuition. Once a selection problem is known to have it, a large body of theory applies, and that is what this path is about.

To state it precisely we need the right object: a set function. You have a ground set of items, call it V, perhaps all possible sensor locations. A set function f assigns a value to every subset S of V, a single number measuring how good that subset is.

For the sensors, f(S) might be the total length of river covered by the sensors in S. For a summary, f(S) might be how much of a document's meaning the sentences in S convey. The empty set has value zero, and adding items generally raises the value.

The optimization problem is then: choose the subset S that maximizes f, usually under a budget such as at most k items. This framing is extremely general, which is both its strength and its curse. Without more structure, finding the best subset means searching exponentially many of them, and is NP-hard.

The key quantity is the marginal gain: how much value one new item e adds to a set S you already have. It is f(S with e added) minus f(S).

Hold the item fixed and vary the set it joins. Adding a sensor to an almost-empty deployment yields a large marginal gain, because it covers fresh river. Adding the same sensor to a large deployment yields a small gain, because most of what it covers is already watched.

Submodularity is precisely the statement that the marginal gain of any fixed item never increases as the set it joins grows. Formally, for any sets S contained in T, and any item e not in T,

f(S + e) - f(S)  >=  f(T + e) - f(T)

Adding e to the smaller set S helps at least as much as adding it to the larger set T. That single inequality is the whole definition, and everything in this path follows from it.

The picture is one item joining two different sets, where one set contains the other. Submodularity says the item is worth at least as much to the smaller set as to the larger one.

This is worth contrasting with two neighbouring properties. A function is modular if every item's gain is the same regardless of the set, like counting: adding one apple always adds one, with no interaction between items. A function is supermodular if gains increase with the set, the opposite of diminishing returns, as when items reinforce each other and the whole exceeds the sum of parts.

Most real selection problems with redundancy or coverage are submodular, because items overlap and later ones repeat what earlier ones already gave. Modularity is the special no-interaction case, and supermodularity, complementary items, is comparatively rare in the selection problems this path targets.

One more distinction shapes everything downstream: whether the function is monotone.

A set function is monotone if adding an item never decreases its value; more is never worse, even if the marginal gain shrinks toward zero. River coverage is monotone: an extra sensor cannot uncover ground you were already watching. So is the reach of a set of advertisements, or the meaning conveyed by a set of sentences.

But some submodular functions are non-monotone, where adding an item can actively hurt. Placing sensors that cost money nets coverage minus cost, so a redundant sensor whose upkeep exceeds its fresh coverage lowers the total. Diversity objectives behave similarly: adding a near-duplicate can reduce a diversity score.

The two cases need different algorithms and carry different guarantees. The clean, strong results in the next lesson are for monotone submodular maximization, the most common case, and the non-monotone case is treated later.

The cleanest submodular function, and the one to keep in mind, is coverage. Each item is a set of elements it covers, and f(S) is the size of the union of the sets you have chosen.

Suppose three websites reach these audiences:

A covers {1, 2, 3, 4}
B covers {3, 4, 5, 6}
C covers {5, 6, 7}

Start empty and add A: gain 4, the whole of A. Now add B to the set containing A: B covers 3,4,5,6 but 3 and 4 are already covered, so the marginal gain is only 2. Add B to the empty set instead and its gain is 4. The gain of B fell from 4 to 2 as the set grew, which is submodularity in action.

Coverage is monotone, since a union only grows, and it is the prototype behind sensor placement, ad reach, and feature or document selection. If you understand coverage, you understand the shape of the whole field.

Submodularity is often called the discrete analog of convexity, and the analogy is worth understanding, because it explains why the property is so powerful.

Convexity, in continuous optimization, is the structural property that makes minimization tractable: local information determines the global optimum, so following the slope downhill works. Submodularity plays a comparable structural role for set functions. As Laszlo Lovasz showed in 1983, every submodular function has a natural continuous extension, the Lovasz extension, that is exactly convex, making the connection formal rather than a loose metaphor.

The practical upshot is a clean split, developed in the coming lessons. Submodular minimization inherits convexity's good behaviour and can be solved exactly in polynomial time. Submodular maximization is NP-hard in general, but the diminishing-returns structure still guarantees that a simple greedy algorithm gets provably close to optimal. Either way, submodularity is what turns a hopeless combinatorial search into something with a guarantee.

Submodularity earns its place in machine learning because so many core tasks are, underneath, the problem of choosing a good subset under a budget.

Which sensors to place, which points to label when labels are costly, which examples to keep as a representative summary of a huge dataset, which features to select, which documents to show: each is a set-selection problem where redundancy makes the objective submodular. Andreas Krause of ETH Zurich, who leads the ETH AI Center, is among the researchers who made submodular optimization a standard tool across these applications, which the third lesson surveys.

The appeal is that a messy, application-specific selection problem, once shown to be submodular, immediately inherits fast algorithms with worst-case guarantees, no bespoke analysis required. Recognizing the structure is most of the work. The next lesson delivers the payoff: the greedy algorithm and the guarantee that made this whole area famous.