Localized Distributional Robustness in Submodular Multi-Task Subset Selection

Ege C. Kaya, Abolfazl Hashemi

Abstract

In this work, we approach the problem of multi-task submodular optimization with the perspective of local distributional robustness, within the neighborhood of a reference distribution which assigns an importance score to each task. We initially propose to introduce a regularization term which makes use of the relative entropy to the standard multi-task objective. We then demonstrate through duality that this novel formulation itself is equivalent to the maximization of a submodular function, which may be efficiently carried out through standard greedy selection methods. This approach bridges the existing gap in the optimization of performance-robustness trade-offs in multi-task subset selection. To numerically validate our theoretical results, we test the proposed method in two different setting, one involving the selection of satellites in low Earth orbit constellations in the context of a sensor selection problem, and the other involving an image summarization task using neural networks. Our method is compared with two other algorithms focused on optimizing the performance of the worst-case task, and on directly optimizing the performance on the reference distribution itself. We conclude that our novel formulation produces a solution that is locally distributional robust, and computationally inexpensive.

Introduction

In multi-task optimization, practitioners often face a fundamental trade-off between average-case performance and worst-case robustness. When selecting a subset of items—such as sensors for environmental monitoring or images for a summary—optimizing for the average performance across all tasks can leave individual tasks vulnerable to failure. Conversely, optimizing strictly for the worst-case scenario (max-min optimization) can be overly pessimistic, often sacrificing significant overall utility to improve a single, potentially intractable "straggler" task.

This paper introduces a framework for Localized Distributional Robustness (DRO) in submodular multi-task subset selection. By focusing on a neighborhood around a reference distribution, the proposed method allows for a tunable balance between these two extremes, ensuring robustness against local perturbations in task importance without the computational overhead typically associated with robust optimization.

Methods

The core of the proposed approach is the introduction of a localized robustness objective. Instead of assuming a fixed weight for each task, the authors consider a set of distributions $P$ within a specific distance from a reference distribution $Q$.

KL Regularization and Duality

The framework employs Relative Entropy (KL divergence) as the distance metric to define the neighborhood around $Q$. The problem is formulated as a minimax optimization: maximizing the subset utility under the least favorable distribution $P$ within the KL-divergence ball.

The geometry of localized distributional robustness within the probability simplex, showing the neighborhood around reference distribution Q.

A key contribution of this work is the application of a duality trick. The authors demonstrate that the inner minimization problem has a closed-form solution when using KL divergence. This transformation collapses the complex minimax problem into the maximization of a single function $G(S)$, which is a composition of a monotone increasing function and a submodular function. This allows the problem to be solved efficiently using standard Stochastic Greedy algorithms, providing distributional robustness at a computational cost comparable to standard non-robust optimization.

Experimental Validation

The method was evaluated in two distinct domains:

  1. LEO Satellite Simulation: A Walker-Delta constellation of 240 satellites was tasked with atmospheric sensing (Lorenz 63 model) and ground coverage. The "Local" approach outperformed the standard Submodular Saturation Algorithm (SSA) by maintaining high average utility while significantly raising the performance floor for the worst-performing tasks.
  2. Image Summarization: Using the Pokemon dataset (819 images) and AlexNet embeddings, the algorithm selected representative subsets. The results confirmed that the localized approach provides a flexible spectrum of robustness, controlled by a regularization parameter $\lambda$. When $\lambda$ is large, the model mimics average-case optimization; as $\lambda$ decreases, it shifts toward global worst-case optimization.

Conclusion

The proposed localized distributional robustness framework bridges the gap between average-case and worst-case submodular optimization. By leveraging KL-divergence duality, the authors provide a method that is both theoretically grounded and computationally efficient. Future work may extend this framework to handle more complex constraints, such as knapsack or matroid constraints, and explore automated methods for hyperparameter tuning to further simplify deployment in real-world systems.

Summary updated

Abstract

In this work, we approach the problem of multi-task submodular optimization with the perspective of local distributional robustness, within the neighborhood of a reference distribution which assigns an importance score to each task. We initially propose to introduce a regularization term which makes use of the relative entropy to the standard multi-task objective. We then demonstrate through duality that this novel formulation itself is equivalent to the maximization of a submodular function, which may be efficiently carried out through standard greedy selection methods. This approach bridges the existing gap in the optimization of performance-robustness trade-offs in multi-task subset selection. To numerically validate our theoretical results, we test the proposed method in two different setting, one involving the selection of satellites in low Earth orbit constellations in the context of a sensor selection problem, and the other involving an image summarization task using neural networks. Our method is compared with two other algorithms focused on optimizing the performance of the worst-case task, and on directly optimizing the performance on the reference distribution itself. We conclude that our novel formulation produces a solution that is locally distributional robust, and computationally inexpensive.
BibTeX
@article{kaya2024localized,
  author = {Ege C. Kaya and Abolfazl Hashemi},
  title = {{Localized Distributional Robustness in Submodular Multi-Task Subset Selection}},
  journal = {IEEE Trans. Signal Process.},
  year = {2024},
  doi = {10.1109/tsp.2024.3492165},
}
Figure