Beyond Greedy: Minimization, Non-Monotone, and Richer Constraints

A fact that catches everyone out: for submodular functions, minimization is easy and maximization is hard, the reverse of the intuition from convex optimization, where minimizing is the tractable direction.

Submodular minimization, finding the subset of least value, can be solved exactly in polynomial time. Submodular maximization, the subject of the last two lessons, is NP-hard and admits only approximation. Same functions, opposite difficulty, depending on which way you optimize.

The reason returns to the convexity analogy. The Lovasz extension of a submodular function is convex, and minimizing a convex function is the tractable problem, so submodular minimization inherits that tractability. Maximizing a convex function, by contrast, is hard, which mirrors why submodular maximization is hard. The analogy is not decorative; it predicts exactly which direction is easy.

Submodular minimization is less famous than maximization but underlies some workhorse tools, especially in computer vision.

The leading example is the graph-cut problems used for image segmentation, separating foreground from background. The energy function these methods minimize is submodular for a wide class of models, which is exactly why it can be minimized efficiently and exactly, rather than only approximately. Many problems phrased as finding a minimum cut in a graph are submodular minimization in disguise.

That submodular minimization is polynomial-time was a landmark theoretical result, first shown through the ellipsoid method by Martin Grotschel, Laszlo Lovasz, and Alexander Schrijver, and later by combinatorial algorithms such as that of Satoru Iwata, Lisa Fleischer, and Satoru Fujishige in 2001. Practically, specialized minimum-cut solvers are used rather than the general algorithms, but the guarantee that an exact answer exists in polynomial time is what makes the whole approach sound.

Return to maximization but drop monotonicity. Recall the coverage-minus-cost objective from the first lesson: a redundant sensor whose upkeep exceeds its fresh coverage lowers the total, so more is not always better.

Plain greedy can fail badly here. It only ever adds items, and it will happily add something with positive marginal gain that a better solution would have left out, unable to ever undo the choice. The monotone guarantee simply does not apply.

Different algorithms are needed. The elegant one is the double greedy algorithm of Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz, from 2015. It runs two passes at once, one starting empty and growing, one starting full and shrinking, and for each item makes a randomized decision to keep or drop it based on both. It achieves a one-half approximation for unconstrained non-monotone submodular maximization, which is known to be the best possible, echoing the tight-bound story from the monotone case.

The cardinality constraint, at most k items, is the simplest budget. Real problems often impose more structure on which subsets are allowed.

A matroid constraint captures rules like choose at most one sensor per region, or keep the selection linearly independent, a common pattern generalizing many natural restrictions. A knapsack constraint captures a total-cost budget, where items have different costs and the sum must stay under a limit, rather than merely a count.

For these, plain greedy's clean (1 - 1/e) guarantee weakens: greedy under a general matroid guarantees only one-half. Recovering the full (1 - 1/e) took a more sophisticated method, the continuous greedy algorithm of Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrak, which optimizes a smooth continuous relaxation called the multilinear extension and then rounds the fractional solution back to a set. It restores the optimal (1 - 1/e) guarantee for any matroid constraint.

That last method points to a deeper idea now central to the field: relax the discrete problem to a continuous one, solve it with smooth optimization, and round back.

The bridge is the multilinear extension, which turns a set function into a function over the unit cube, where a coordinate is the probability of including an item. This continuous surface can be optimized by gradient-style methods, and its maximum guides which fractional selection is best. A rounding step then converts those probabilities into an actual subset while preserving most of the value.

This continuous perspective, and the Lovasz extension behind submodular minimization, are two instances of the same move: a combinatorial problem over discrete sets becomes a continuous optimization problem with structure. Much of modern submodular optimization lives in that translation, because the continuous side connects to the vast, well-developed machinery of convex and smooth optimization.

The whole territory fits on one map, organized by the two questions that decide which tool to use: are you minimizing or maximizing, and if maximizing, is the function monotone and what constrains the choice.

The reassuring pattern is that every box has a known, principled answer with a proven guarantee. The first three lessons lived in the second row, the most common case, and it is worth mastering first. But knowing the whole table means that when a real problem turns out non-monotone, or budget-constrained by cost, or a minimization, you know a guaranteed method exists and which one to reach for.

Once you can recognize the property, it shows up across machine learning, often unlabelled.

Active learning chooses which points to label under a budget, a submodular coverage of the space. Data subset selection and coreset construction pick a representative sample of a huge dataset to cut training cost, a summarization objective. Feature selection under redundancy is approximately submodular. Determinantal point processes, a probabilistic model of diverse sets, have a log-probability that is submodular, tying diversity directly to the theory. Even some neural-network compression and dictionary-selection problems fall into the same frame.

The common signature is always the same: choosing a subset where items overlap or interfere, so that value has diminishing returns. Whenever you meet that signature, the toolkit from this path applies, and much of that toolkit's transfer into machine learning is due to Andreas Krause and collaborators, whose survey with Daniel Golovin is a standard entry point.

Submodularity is diminishing returns made exact, and it is one of the most useful structural properties in optimization because it turns intractable selection problems into ones with guarantees.

The path in one arc: the diminishing-returns definition and its convexity analogy; the greedy algorithm and the (1 - 1/e) bound that is provably the best possible; the applications, sensors, influence, summaries, that are all the same problem underneath; and this final map, where minimization is exact, non-monotone maximization has its own tight one-half method, and richer constraints are handled by continuous relaxation.

The single habit worth keeping is the reduction. When you face a problem of picking a good subset under a budget, ask whether the objective is monotone and whether it has diminishing returns. If yes, you are not facing an intractable search. You are facing a solved problem with an algorithm and a guarantee, and recognizing that is most of the battle.