Graph Coloring for Multi-Task Learning

• URL: http://arxiv.org/abs/2509.16959v3
• Date: Sat, 18 Oct 2025 02:15:20 GMT
• Title: Graph Coloring for Multi-Task Learning
• Authors: Santosh Patapati,
• Abstract summary: SON-GOKU scheduler computes interference, constructs an interference graph, and applies greedy graph-coloring to tasks.<n>Grouping and sequential updates improve multi-task learning, with guarantees on descent, convergence, and accurately identifying what tasks conflict or align.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When different objectives conflict with each other in multi-task learning, gradients begin to interfere and slow convergence, thereby potentially reducing the final model's performance. To address this, we introduce SON-GOKU, a scheduler that computes gradient interference, constructs an interference graph, and then applies greedy graph-coloring to partition tasks into groups that align well with each other. At each training step, only one group (color class) of tasks are activated, and the grouping partition is constantly recomputed as task relationships evolve throughout training. By ensuring that each mini-batch contains only tasks that pull the model in the same direction, our method improves the effectiveness of any underlying multi-task learning optimizer without additional tuning. Since tasks within these groups will update in compatible directions, multi-task learning will improve model performance rather than impede it. Empirical results on six different datasets show that this interference-aware graph-coloring approach consistently outperforms baselines and state-of-the-art multi-task optimizers. We provide extensive theory showing why grouping and sequential updates improve multi-task learning, with guarantees on descent, convergence, and accurately identifying what tasks conflict or align.

Related papers

• Ensemble Prediction of Task Affinity for Efficient Multi-Task Learning [8.604749005323557]
  We propose ETAP (Ensemble Task Affinity Predictor), a scalable framework that integrates principled and data-driven estimators to predict MTL performance gains.<n>We demonstrate that ETAP improves MTL gain prediction and enables more effective task grouping, outperforming state-of-the-art baselines across diverse application domains.
  arXiv  Detail & Related papers  (2026-02-20T19:57:38Z)
• HGMP:Heterogeneous Graph Multi-Task Prompt Learning [18.703129208282913]
  We propose a novel multi-task prompt framework for the heterogeneous graph domain, named HGMP.<n>First, to bridge the gap between the pre-trained model and downstream tasks, we reformulate all downstream tasks into a unified graph-level task format.<n>We design a graph-level contrastive pre-training strategy to better leverage heterogeneous information and enhance performance in multi-task scenarios.
  arXiv  Detail & Related papers  (2025-07-10T04:01:47Z)
• AdaRank: Adaptive Rank Pruning for Enhanced Model Merging [15.383220675351076]
  Model merging has emerged as a promising approach for unifying independently fine-tuned models into an integrated framework.<n>We propose AdaRank, a novel model merging framework that adaptively selects the most beneficial singular directions of task vectors to merge multiple models.<n>AdaRank consistently achieves state-of-the-art performance with various backbones and number of tasks, reducing the performance gap between fine-tuned models to nearly 1%.
  arXiv  Detail & Related papers  (2025-03-28T06:49:06Z)
• Selective Task Group Updates for Multi-Task Optimization [44.601029688423914]
  We introduce an algorithm that adaptively determines how to effectively group tasks and update them during the learning process.<n>Our methods substantially outperform previous multi-task optimization approaches.
  arXiv  Detail & Related papers  (2025-02-17T16:26:05Z)
• Modeling Multi-Task Model Merging as Adaptive Projective Gradient Descent [72.10987117380584]
  Merging multiple expert models offers a promising approach for performing multi-task learning without accessing their original data.<n>We find existing methods discard task-specific information that, while causing conflicts, is crucial for performance.<n>Our approach consistently outperforms previous methods, achieving state-of-the-art results across diverse architectures and tasks in both vision and NLP domains.
  arXiv  Detail & Related papers  (2025-01-02T12:45:21Z)
• ForkMerge: Mitigating Negative Transfer in Auxiliary-Task Learning [59.08197876733052]
  Auxiliary-Task Learning (ATL) aims to improve the performance of the target task by leveraging the knowledge obtained from related tasks. Sometimes, learning multiple tasks simultaneously results in lower accuracy than learning only the target task, known as negative transfer. ForkMerge is a novel approach that periodically forks the model into multiple branches, automatically searches the varying task weights.
  arXiv  Detail & Related papers  (2023-01-30T02:27:02Z)
• 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)
• Leveraging convergence behavior to balance conflicting tasks in multi-task learning [3.6212652499950138]
  Multi-Task Learning uses correlated tasks to improve performance generalization. Tasks often conflict with each other, which makes it challenging to define how the gradients of multiple tasks should be combined. We propose a method that takes into account temporal behaviour of the gradients to create a dynamic bias that adjust the importance of each task during the backpropagation.
  arXiv  Detail & Related papers  (2022-04-14T01:52:34Z)
• Conflict-Averse Gradient Descent for Multi-task Learning [56.379937772617]
  A major challenge in optimizing a multi-task model is the conflicting gradients. We introduce Conflict-Averse Gradient descent (CAGrad) which minimizes the average loss function. CAGrad balances the objectives automatically and still provably converges to a minimum over the average loss.
  arXiv  Detail & Related papers  (2021-10-26T22:03:51Z)
• Sequential Reptile: Inter-Task Gradient Alignment for Multilingual Learning [61.29879000628815]
  We show that it is crucial for tasks to align gradients between them in order to maximize knowledge transfer. We propose a simple yet effective method that can efficiently align gradients between tasks. We extensively validate our method on various multi-task learning and zero-shot cross-lingual transfer tasks.
  arXiv  Detail & Related papers  (2021-10-06T09:10:10Z)
• Efficiently Identifying Task Groupings for Multi-Task Learning [55.80489920205404]
  Multi-task learning can leverage information learned by one task to benefit the training of other tasks. We suggest an approach to select which tasks should train together in multi-task learning models. Our method determines task groupings in a single training run by co-training all tasks together and quantifying the effect to which one task's gradient would affect another task's loss.
  arXiv  Detail & Related papers  (2021-09-10T02:01:43Z)
• Multi-task Over-the-Air Federated Learning: A Non-Orthogonal Transmission Approach [52.85647632037537]
  We propose a multi-task over-theair federated learning (MOAFL) framework, where multiple learning tasks share edge devices for data collection and learning models under the coordination of a edge server (ES) Both the convergence analysis and numerical results demonstrate that the MOAFL framework can significantly reduce the uplink bandwidth consumption of multiple tasks without causing substantial learning performance degradation.
  arXiv  Detail & Related papers  (2021-06-27T13:09:32Z)
• Multi-task Supervised Learning via Cross-learning [102.64082402388192]
  We consider a problem known as multi-task learning, consisting of fitting a set of regression functions intended for solving different tasks. In our novel formulation, we couple the parameters of these functions, so that they learn in their task specific domains while staying close to each other. This facilitates cross-fertilization in which data collected across different domains help improving the learning performance at each other task.
  arXiv  Detail & Related papers  (2020-10-24T21:35:57Z)
• Gradient Surgery for Multi-Task Learning [119.675492088251]
  Multi-task learning has emerged as a promising approach for sharing structure across multiple tasks. The reasons why multi-task learning is so challenging compared to single-task learning are not fully understood. We propose a form of gradient surgery that projects a task's gradient onto the normal plane of the gradient of any other task that has a conflicting gradient.
  arXiv  Detail & Related papers  (2020-01-19T06:33:47Z)

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.