In many real-world selection problems, we are looking for a subset of items that provides the most "value." If that value follows the law of diminishing returns—where adding an item to a small set helps more than adding it to a large set—we call the objective function submodular.
Standard algorithms, like the classic greedy approach, are excellent at maximizing a single submodular function. However, real-world systems rarely have just one goal. A network designer must balance signal quality across diverse user groups; a machine learning researcher must balance model accuracy with fairness; and a procurement officer must balance cost against multiple quality metrics.
When we move from one objective to many, we enter the realm of Robust Multi-Objective Submodular Maximization. The goal shifts from maximizing the average performance to ensuring a high "floor" for all objectives simultaneously.
The Robustness Gap
The most common way to frame multi-objective optimization is the max-min objective: find a set $S$ that maximizes the minimum value among several submodular functions $f_1, f_2, \dots, f_k$.
As Nima Anari and Sebastian Pokutta observe in Robust Submodular Maximization: Offline and Online Algorithms, this is significantly harder than standard maximization. In a single-objective greedy algorithm, you always pick the element that adds the most value. But in a max-min setting, the "worst" function might change every time you add an element. A choice that helps $f_1$ might do nothing for $f_2$, which is currently the bottleneck.
If you optimize only for the average case, you risk creating "blind spots" where certain criteria are completely ignored. Praneeth Vepakomma and colleagues argue in Parallel Quasi-concave set optimization that maximizing the minimum relationship (a maxi-min objective) is the only way to ensure that the least-represented element or objective is of sufficient quality.
Bi-criteria Approximations: Trading Constraints for Performance
Because finding an exact solution to the max-min problem is often computationally intractable, researchers use bi-criteria approximations. Instead of trying to find the perfect set of size $K$, these algorithms allow themselves a slightly larger budget (e.g., $2K$ or $K/\epsilon$) to guarantee they can meet a specific fraction of the optimal value for every objective.
Rajan Udwani demonstrates in Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint that iterative weighting strategies—where the algorithm dynamically increases the importance of the currently "weakest" objective—can bridge the gap between slow exact methods and fast heuristics.
This bi-criteria approach is particularly powerful in mechanism design. Amin Karbasi and Vahab Mirrokni show in Procurement Auctions via Approximately Optimal Submodular Optimization that by slightly relaxing constraints, they can create auctions that are incentive-compatible and robust, effectively reaching the theoretical Pareto frontier—the set of solutions where you cannot improve one objective without hurting another.
Soft Robustness and Quantiles
The absolute worst-case (max-min) objective can sometimes be too conservative, especially if one objective is an outlier or impossible to satisfy. To handle this, researchers have developed "softer" versions of robustness.
- The Quantile Approach: Instead of maximizing the minimum, Cedric Malherbe and Kevin Scaman introduce SOFTSAT in Robustness in Multi-Objective Submodular Optimization: a Quantile Approach. They maximize a specific quantile (e.g., the bottom 10%), which provides a more flexible trade-off than the absolute minimum.
- Mixed Objectives: Kai Wei and Jeff Bilmes propose a framework in Mixed Robust/Average Submodular Partitioning that optimizes a weighted combination of the average and the worst-case. This ensures that the system is efficient on average while remaining "fair" to all subsets.
- Soft-Min Functions: In online settings where data arrives in a stream, Nima Anari and Nika Haghtalab use "soft-min" functions—smooth approximations of the minimum—to handle adversarial data without the mathematical "jumps" that make standard min-functions difficult to optimize.
Why It Works: The Power of Diminishing Returns
The reason these robust frameworks are possible is that submodularity provides a predictable structure. Even when we are juggling multiple objectives, the property of diminishing returns allows us to use greedy-like variants—such as the Distorted Greedy algorithm analyzed by Yuan Deng and colleagues—to explore the trade-offs between different goals.
By leveraging submodularity, we can move from "best-guess" heuristics to algorithms with provable guarantees. Whether it's pruning phrase tables in translation tasks (Jun Suzuki) or selecting model structures that are stable under adversarial perturbations (Jonathan Bunton), robust submodular optimization ensures that our "optimal" solutions don't fail when they encounter the complexity of the real world.