# Localized Distributional Robustness in Submodular Multi-Task Subset Selection

arXiv: https://arxiv.org/abs/2404.03759 · HTML: https://mlsanity.com/paper/2404.03759/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 58 references that are in the map.
- First posted on arXiv 4 Apr 2024.

## Builds on (most cited first, 14 of 14)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Faster Non-Convex Federated Learning via Global and Local Momentum](https://mlsanity.com/paper/2012.04061/) (2020)
- [An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2006.10138/) (2020)
- [Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints](https://mlsanity.com/paper/1311.2106/) (2013)
- [Robust Submodular Maximization: A Non-Uniform Partitioning Approach](https://mlsanity.com/paper/1706.04918/) (2017)
- [Distributionally Robust Submodular Maximization](https://mlsanity.com/paper/1802.05249/) (2018)
- [Submodular Observation Selection and Information Gathering for Quadratic Models](https://mlsanity.com/paper/1905.09919/) (2019)
- [Randomized Greedy Sensor Selection: Leveraging Weak Submodularity](https://mlsanity.com/paper/1807.08627/) (2018)
- [A Randomized Greedy Algorithm for Near-Optimal Sensor Scheduling in Large-Scale Sensor Networks](https://mlsanity.com/paper/1709.08823/) (2017)
- [Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint](https://mlsanity.com/paper/1711.06428/) (2017)
- [Approximate Supermodularity Bounds for Experimental Design](https://mlsanity.com/paper/1711.01501/) (2017)
- [Robust and Adaptive Sequential Submodular Optimization](https://mlsanity.com/paper/1909.11783/) (2019)

## Built on by (most cited first, 1 of 1)

- [Submodular Maximization Approaches for Equitable Client Selection in Federated Learning](https://mlsanity.com/paper/2408.13683/) (2024)

## Abstract (arXiv)

In this work, we treat the problem of multi-task submodular optimization from 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 relative-entropy regularization term to the standard multi-task objective. We then demonstrate through duality that this novel formulation itself is equivalent to the maximization of a monotone increasing function composed with 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 settings, one on the selection of satellites in low Earth orbit constellations in the context of a sensor selection problem involving weak-submodular functions, and the other on an image summarization task using neural networks involving submodular functions. 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.