Localized Distributional Robustness in Submodular Multi-Task Subset Selection

• URL: http://arxiv.org/abs/2404.03759v2
• Date: Sun, 03 Nov 2024 21:08:23 GMT
• Title: Localized Distributional Robustness in Submodular Multi-Task Subset Selection
• Authors: Ege C. Kaya, Abolfazl Hashemi,
• Abstract summary: We propose a regularization term which makes use of the relative entropy to the standard multi-task objective. We show that this novel formulation is equivalent to a monotone increasing function composed with a submodular function. We conclude that our novel formulation produces a solution that is locally distributional robust, and computationally inexpensive.
• Score: 5.116582735311639
• License:
• 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 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.

Related papers

• Consistent Submodular Maximization [27.266085572522847]
  maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper we study this problem in a dynamic environment with consistency constraints: elements arrive in a streaming fashion and the goal is maintaining a constant approximation to the optimal solution while having a stable solution. We provide algorithms in this setting with different trade-offs between consistency and approximation quality.
  arXiv  Detail & Related papers  (2024-05-30T11:59:58Z)
• Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
  This research presents a method to meet requirements through the minimization objective function of the RPM algorithm. A branch-and-bound (BnB) algorithm is devised, which solely branches over the parameters, thereby boosting convergence rate. Empirical evaluations demonstrate better robustness of the proposed methodology against non-rigid deformation, positional noise, and outliers, when compared with prevailing state-of-the-art transformations.
  arXiv  Detail & Related papers  (2024-05-14T13:28:57Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback [106.63518036538163]
  We present a novel unified bilevel optimization-based framework, textsfPARL, formulated to address the recently highlighted critical issue of policy alignment in reinforcement learning. Our framework addressed these concerns by explicitly parameterizing the distribution of the upper alignment objective (reward design) by the lower optimal variable. Our empirical results substantiate that the proposed textsfPARL can address the alignment concerns in RL by showing significant improvements.
  arXiv  Detail & Related papers  (2023-08-03T18:03:44Z)
• Moreau-Yoshida Variational Transport: A General Framework For Solving Regularized Distributional Optimization Problems [3.038642416291856]
  We consider a general optimization problem of minimizing a composite objective functional defined over a class probability distributions. We propose a novel method, dubbed as Moreau-Yoshida Variational Transport (MYVT), for solving the regularized distributional optimization problem.
  arXiv  Detail & Related papers  (2023-07-31T01:14:42Z)
• Efficient Alternating Minimization Solvers for Wyner Multi-View Unsupervised Learning [0.0]
  We propose two novel formulations that enable the development of computational efficient solvers based the alternating principle. The proposed solvers offer computational efficiency, theoretical convergence guarantees, local minima complexity with the number of views, and exceptional accuracy as compared with the state-of-the-art techniques.
  arXiv  Detail & Related papers  (2023-03-28T10:17:51Z)
• On the implementation of a global optimization method for mixed-variable problems [0.30458514384586394]
  The algorithm is based on the radial basis function of Gutmann and the metric response surface method of Regis and Shoemaker. We propose several modifications aimed at generalizing and improving these two algorithms.
  arXiv  Detail & Related papers  (2020-09-04T13:36:56Z)
• A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features [52.856801164425086]
  We study multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) coupling function.
  arXiv  Detail & Related papers  (2020-06-15T19:40:24Z)
• Distributionally Robust Bayesian Optimization [121.71766171427433]
  We present a novel distributionally robust Bayesian optimization algorithm (DRBO) for zeroth-order, noisy optimization. Our algorithm provably obtains sub-linear robust regret in various settings. We demonstrate the robust performance of our method on both synthetic and real-world benchmarks.
  arXiv  Detail & Related papers  (2020-02-20T22:04:30Z)
• Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
  We consider distributed optimization problems where forming the Hessian is computationally challenging and communication is a bottleneck. We develop unbiased parameter averaging methods for randomized second order optimization that employ sampling and sketching of the Hessian. We also extend the framework of second order averaging methods to introduce an unbiased distributed optimization framework for heterogeneous computing systems.
  arXiv  Detail & Related papers  (2020-02-16T09:01:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.