Robustness in Multi-Objective Submodular Optimization: a Quantile Approach

Cédric Malherbe, Kevin ScamanICML 2022 · OpenReview

Overview

This paper introduces SOFTSAT, a novel algorithm for robust multi-objective submodular optimization. Instead of focusing on maximizing the average or worst-case performance, SOFTSAT targets the maximization of quantiles. By leveraging "biased expectations" as a submodularity-preserving proxy, the authors provide the first theoretical approximation guarantees for this computationally challenging class of problems.

The Problem: Beyond Average and Worst-Case

Submodular optimization is a cornerstone of machine learning, used for tasks ranging from feature selection to sensor placement. While efficient greedy algorithms exist for single objectives, real-world systems often involve multiple, competing submodular objectives—such as ensuring high signal quality for many users in a wireless network.

Standard approaches typically optimize for either the average case or the worst case, but both have significant flaws:

  • Average-case optimization can ignore outliers and lead to highly unfair resource allocation.
  • Worst-case optimization is often too pessimistic, allowing a single "bad" objective or outlier to dictate the entire system's performance.

Maximizing the $p$-th quantile offers a robust middle ground. It ensures a good value for at least $(1-p)$ percent of the objectives, effectively ignoring extreme outliers while maintaining fairness. However, quantiles are notoriously difficult to optimize because they do not preserve the submodularity property that makes greedy algorithms effective. In fact, directly approximating the optimal quantile is NP-hard.

Comparison of average-case, worst-case, and quantile allocations. Quantiles provide a better balance between overall performance and fairness.

Methodology: Biased Expectations as a Proxy

The core innovation of this paper is the introduction of biased expectations ($\mu_s$) as a smooth proxy for the quantile function.

  1. The Proxy: Biased expectations interpolate between the minimum (as $s \to -\infty$), the mean ($s \to 0$), and the maximum ($s \to +\infty$) of a set of values.
  2. Submodularity Conservation: Crucially, the authors prove that for $s < 0$, the biased expectation of a collection of submodular functions remains "submodular-like." Specifically, it acts as a composition of a strictly increasing function and a submodular function, meaning it can be efficiently optimized using a greedy approach.
  3. The SOFTSAT Algorithm: The proposed algorithm, SOFTSAT, is a greedy procedure that sequentially adds elements to a set to maximize the marginal gain of this biased expectation.
  4. Theoretical Guarantees: The paper provides approximation ratios for SOFTSAT, demonstrating that it can achieve a non-zero approximation of the optimal quantile even in regimes where standard methods fail.
Visualizing how biased expectations shift weight across a distribution based on the parameter s.

Experimental Validation

The authors evaluated SOFTSAT on three diverse real-world applications:

  • Balanced News Feed: Selecting a subset of articles from the BBC news dataset ($n=2250$) to fairly cover 10 different topics.
  • Image Summarization: Selecting representative images from a Pokemon dataset ($n=151$) while ignoring outliers, using embeddings from a pre-trained AlexNet.
  • Graph Covering: Placing source nodes in a graph to communicate with a high percentage of other nodes, using the USAirport 500 dataset.

Across all benchmarks, SOFTSAT consistently outperformed or matched state-of-the-art methods like SATURATE and GreedyQuantile. For instance, in the image summarization task with $p=0.4$, SOFTSAT reached the maximum possible value with only $K=41$ images, whereas other methods required up to $K=50$. Furthermore, an "adaptive" version of the algorithm (AdaSOFTSAT), which tunes the parameter $s$ on the fly, proved particularly effective and computationally efficient for real-time applications.

Key Insights and Future Directions

  • Quantiles as Fairness: Quantile maximization serves as a tool for "robust fairness," allowing practitioners to discard a small percentage of outliers to significantly boost performance for the majority.
  • The Power of Proxies: Transitioning from a hard, non-submodular objective to a tractable, submodular-preserving proxy is the key breakthrough, turning an inapproximable problem into one with provable bounds.
  • Limitations: While heuristics like grid search and adaptive updates help tune the parameter $s$, finding the strictly "optimal" $s$ for a specific quantile $p$ remains somewhat empirical. Additionally, some theoretical bounds depend on problem-specific constants.
  • Future Work: Extending this framework to more complex combinatorial constraints beyond simple cardinality (e.g., matroid or knapsack constraints) is a natural next step for the field.

Summary updated

Abstract

The optimization of multi-objective submodular systems appears in a wide variety of applications. However, there are currently very few techniques which are able to provide a robust allocation to s...
BibTeX
@inproceedings{malherbe2022robustness,
  author = {Cédric Malherbe and Kevin Scaman},
  title = {{Robustness in Multi-Objective Submodular Optimization: a Quantile Approach}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=NnUpxs5_gsu},
}
Figure