Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints

• URL: http://arxiv.org/abs/2608.10425v2
• Date: Thu, 13 Aug 2026 04:03:01 GMT
• Title: Multitask Pareto Optimization for Monotone Submodular Problems with Dynamic Constraints
• Abstract summary: We study a multitasking formulation in which all tasks share a common monotone submodular function $f$, but differ in their constraints.<n>This enables solution sharing across tasks and can improve performance compared to running standard evolutionary approaches independently.
• Score: 6.164863213336097
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary multitasking is a recent approach that solves multiple related optimization problems within a single evolutionary run, rather than addressing each problem separately. We consider monotone submodular optimization problems with dynamic knapsack constraints and study a multitasking formulation in which all tasks share a common monotone submodular function $f$, but differ in their constraints. We focus on the case where elements within each constraint have uniform cost and show that this structure leads to small Pareto fronts in the multitasking formulation. This enables solution sharing across tasks and can improve performance compared to running standard evolutionary approaches independently, depending on the constraint regime. Using rigorous runtime analysis, we analyze the expected time until the proposed multitasking algorithms obtain a $(1 - 1/e)$-approximation for each task. Experimental results for the Maximum Coverage problem complement the theoretical analysis and provide further insight into the practical behavior of the approach across different budget settings.

Related papers

• Analysis of Multitasking Pareto Optimization for Monotone Submodular Problems [6.164863213336097]
  We introduce multitasking formulations of problems that are an effective way to solve multiple related problems with a single run.<n>Using rigorous runtime analysis, we analyze the expected time until the introduced multitasking approaches obtain a $(1-1/e)$-approximation for each of the given problems.
  arXiv  Detail & Related papers  (2026-04-16T14:31:19Z)
• Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection [60.07018090570548]
  We introduce a novel algorithm titled MultinoulliSCG, which is parameterfree and can achieve the same approximation guarantees as the distorted local-search methods.<n>We also present two novel online algorithms, namely, Multinoulli-CG and Multinoulli-GAGA, for the unexplored online subset selection problems over partition constraints.
  arXiv  Detail & Related papers  (2026-03-23T02:30:01Z)
• 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)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours.<n>We focus on the case of linear utility functions parametrised by weight vectors w.<n>We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Multi-Task Learning with Multi-Task Optimization [31.518330903602095]
  We show that a set of optimized yet well-distributed models embody different trade-offs in one algorithmic pass. We investigate the proposed multi-task learning with multi-task optimization for solving various problem settings.
  arXiv  Detail & Related papers  (2024-03-24T14:04:40Z)
• Pareto Manifold Learning: Tackling multiple tasks via ensembles of single-task models [50.33956216274694]
  In Multi-Task Learning (MTL), tasks may compete and limit the performance achieved on each other, rather than guiding the optimization to a solution. We propose textitPareto Manifold Learning, an ensembling method in weight space.
  arXiv  Detail & Related papers  (2022-10-18T11:20:54Z)
• In Defense of the Unitary Scalarization for Deep Multi-Task Learning [121.76421174107463]
  We present a theoretical analysis suggesting that many specialized multi-tasks can be interpreted as forms of regularization. We show that, when coupled with standard regularization and stabilization techniques, unitary scalarization matches or improves upon the performance of complex multitasks.
  arXiv  Detail & Related papers  (2022-01-11T18:44:17Z)
• Small Towers Make Big Differences [59.243296878666285]
  Multi-task learning aims at solving multiple machine learning tasks at the same time. A good solution to a multi-task learning problem should be generalizable in addition to being Pareto optimal. We propose a method of under- parameterized self-auxiliaries for multi-task models to achieve the best of both worlds.
  arXiv  Detail & Related papers  (2020-08-13T10:45:31Z)
• Efficient Continuous Pareto Exploration in Multi-Task Learning [34.41682709915956]
  We present a novel, efficient method for continuous analysis of optimal solutions in machine learning problems. We scale up theoretical results in multi-objective optimization to modern machine learning problems by proposing a sample-based sparse linear system.
  arXiv  Detail & Related papers  (2020-06-29T23:36:20Z)
• Pareto Multi-Task Learning [53.90732663046125]
  Multi-task learning is a powerful method for solving multiple correlated tasks simultaneously. It is often impossible to find one single solution to optimize all the tasks, since different tasks might conflict with each other. Recently, a novel method is proposed to find one single Pareto optimal solution with good trade-off among different tasks by casting multi-task learning as multiobjective optimization.
  arXiv  Detail & Related papers  (2019-12-30T08:58:40Z)

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.