Efficient Training of Multi-task Neural Solver for Combinatorial Optimization

• URL: http://arxiv.org/abs/2305.06361v4
• Date: Thu, 03 Apr 2025 11:31:44 GMT
• Title: Efficient Training of Multi-task Neural Solver for Combinatorial Optimization
• Authors: Chenguang Wang, Zhang-Hua Fu, Pinyan Lu, Tianshu Yu,
• Abstract summary: We propose a general and efficient training paradigm to deliver a unified multi-task neural solver.<n>Our method significantly enhances overall performance, regardless of whether it is within constrained training budgets.<n>Our method also achieved the best results compared to single task learning and multitask learning approaches.
• Score: 23.694457372640912
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Efficiently training a multi-task neural solver for various combinatorial optimization problems (COPs) has been less studied so far. Naive application of conventional multi-task learning approaches often falls short in delivering a high-quality, unified neural solver. This deficiency primarily stems from the significant computational demands and a lack of adequate consideration for the complexities inherent in COPs. In this paper, we propose a general and efficient training paradigm to deliver a unified combinatorial multi-task neural solver. To this end, we resort to the theoretical loss decomposition for multiple tasks under an encoder-decoder framework, which enables more efficient training via proper bandit task-sampling algorithms through an intra-task influence matrix. By employing theoretically grounded approximations, our method significantly enhances overall performance, regardless of whether it is within constrained training budgets, across equivalent training epochs, or in terms of generalization capabilities, when compared to conventional training schedules. On the real-world datasets of TSPLib and CVRPLib, our method also achieved the best results compared to single task learning and multi-task learning approaches. Additionally, the influence matrix provides empirical evidence supporting common practices in the field of learning to optimize, further substantiating the effectiveness of our approach. Our code is open-sourced and available at https://github.com/LOGO-CUHKSZ/MTL-COP.

Related papers

• A Theoretical Framework for Data Efficient Multi-Source Transfer Learning Based on Cramér-Rao Bound [16.49737340580437]
  We propose a theoretical framework that answers the question: what is the optimal quantity of source samples needed from each source task to jointly train the target model? Specifically, we introduce a generalization error measure that aligns with cross-entropy loss, and minimize it based on the Cram'er-Rao Bound to determine the optimal transfer quantity for each source task. We develop an architecture-agnostic and data-efficient algorithm OTQMS to implement our theoretical results for training deep multi-source transfer learning models.
  arXiv  Detail & Related papers  (2025-02-06T17:32:49Z)
• Learning for Cross-Layer Resource Allocation in MEC-Aided Cell-Free Networks [71.30914500714262]
  Cross-layer resource allocation over mobile edge computing (MEC)-aided cell-free networks can sufficiently exploit the transmitting and computing resources to promote the data rate. Joint subcarrier allocation and beamforming optimization are investigated for the MEC-aided cell-free network from the perspective of deep learning.
  arXiv  Detail & Related papers  (2024-12-21T10:18:55Z)
• Efficient Pareto Manifold Learning with Low-Rank Structure [31.082432589391953]
  Multi-task learning is inherently a multi-objective optimization problem. We propose a novel approach that integrates a main network with several low-rank matrices. It significantly reduces the number of parameters and facilitates the extraction of shared features.
  arXiv  Detail & Related papers  (2024-07-30T11:09:27Z)
• Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Tasks [53.44714413181162]
  This paper shows that when an agent is trained on a sufficiently diverse set of tasks, a generic policy-sharing algorithm with myopic exploration design can be sample-efficient. To the best of our knowledge, this is the first theoretical demonstration of the "exploration benefits" of MTRL.
  arXiv  Detail & Related papers  (2024-03-03T22:57:44Z)
• Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization [35.09656455088854]
  We propose an efficient meta neural vector (EMNH) to solve multi-objective optimization problems. EMNH is able to outperform the state-of-the-art neurals in terms of solution quality and learning efficiency.
  arXiv  Detail & Related papers  (2023-10-22T08:59:02Z)
• Scalarization for Multi-Task and Multi-Domain Learning at Scale [15.545810422759295]
  Training a single model on multiple input domains and/or output tasks allows for compressing information from multiple sources into a unified backbone. However, optimizing such networks is a challenge due to discrepancies between the different tasks or domains.
  arXiv  Detail & Related papers  (2023-10-13T07:31:04Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs) MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
  arXiv  Detail & Related papers  (2023-09-02T11:01:16Z)
• Multi-Objective Optimization for Sparse Deep Multi-Task Learning [0.0]
  We present a Multi-Objective Optimization algorithm using a modified Weighted Chebyshev scalarization for training Deep Neural Networks (DNNs) Our work aims to address the (economical and also ecological) sustainability issue of DNN models, with particular focus on Deep Multi-Task models.
  arXiv  Detail & Related papers  (2023-08-23T16:42:27Z)
• DL-DRL: A double-level deep reinforcement learning approach for large-scale task scheduling of multi-UAV [65.07776277630228]
  We propose a double-level deep reinforcement learning (DL-DRL) approach based on a divide and conquer framework (DCF) Particularly, we design an encoder-decoder structured policy network in our upper-level DRL model to allocate the tasks to different UAVs. We also exploit another attention based policy network in our lower-level DRL model to construct the route for each UAV, with the objective to maximize the number of executed tasks.
  arXiv  Detail & Related papers  (2022-08-04T04:35:53Z)
• Federated Learning with a Sampling Algorithm under Isoperimetry [9.990687944474738]
  Federated learning uses a set of techniques to efficiently distribute the training of a machine learning algorithm across several devices. We propose a communication-efficient variant of Langevinvin's sample a posteriori.
  arXiv  Detail & Related papers  (2022-06-02T08:19:03Z)
• 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)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• An Efficient Application of Neuroevolution for Competitive Multiagent Learning [0.0]
  NEAT is a popular evolutionary strategy used to obtain the best performing neural network architecture. This paper utilizes the NEAT algorithm to achieve competitive multiagent learning on a modified pong game environment.
  arXiv  Detail & Related papers  (2021-05-23T10:34:48Z)
• Efficient Reinforcement Learning in Resource Allocation Problems Through Permutation Invariant Multi-task Learning [6.247939901619901]
  We show that in certain settings, the available data can be dramatically increased through a form of multi-task learning. We provide a theoretical performance bound for the gain in sample efficiency under this setting. This motivates a new approach to multi-task learning, which involves the design of an appropriate neural network architecture and a prioritized task-sampling strategy.
  arXiv  Detail & Related papers  (2021-02-18T14:13:02Z)
• A Low Complexity Decentralized Neural Net with Centralized Equivalence using Layer-wise Learning [49.15799302636519]
  We design a low complexity decentralized learning algorithm to train a recently proposed large neural network in distributed processing nodes (workers) In our setup, the training data is distributed among the workers but is not shared in the training process due to privacy and security concerns. We show that it is possible to achieve equivalent learning performance as if the data is available in a single place.
  arXiv  Detail & Related papers  (2020-09-29T13:08:12Z)
• 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)
• 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.