Localized Distributional Robustness in Submodular Multi-Task Subset
  Selection
Ege C. Kaya Abolfazl Hashemi
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.