Data-efficient Supervised Learning is Powerful for Neural Combinatorial Optimization
Lists
Only you see this
Abstract
Neural combinatorial optimization (NCO) is a promising learning-based approach to solve difficult combinatorial optimization problems. However, how to efficiently train a powerful NCO solver remains challenging. The widely-used reinforcement learning method suffers from sparse rewards and low data efficiency, while the supervised learning approach requires a large number of high-quality solutions. In this work, we develop efficient methods to extract sufficient supervised information from limited labeled data, which can significantly overcome the main shortcoming of supervised learning. To be specific, we propose a set of efficient data augmentation methods and a novel bidirectional loss to better leverage the equivalent properties of problem instances, which finally lead to a promising supervised learning approach. The thorough experimental studies demonstrate our proposed method can achieve state-of-the-art performance on the traveling salesman problem (TSP) only with a small set of 50,000 labeled instances, while it also enjoys better generalization performance. We believe this somewhat surprising finding could lead to valuable rethinking on the value of efficient supervised learning for NCO.
BibTeX
@inproceedings{yao2023data,
author = {Shunyu Yao and Xi Lin and Zhenkun Wang and Qingfu Zhang},
title = {{Data-efficient Supervised Learning is Powerful for Neural Combinatorial Optimization}},
booktitle = {International Conference on Learning Representations},
year = {2023},
url = {https://openreview.net/forum?id=a_yFkJ4-uEK},
}Loading related content...