Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning
This work addresses a key limitation in applying unsupervised learning to combinatorial optimization, offering a more adaptive approach for researchers and practitioners in optimization and AI.
The paper tackles the misalignment in unsupervised learning for combinatorial optimization by proposing a meta-learning-based training pipeline that searches for good initializations rather than direct solutions, achieving significant empirical performance improvements where initial solutions outperform baselines across multiple datasets and problem scales.
A general framework of unsupervised learning for combinatorial optimization (CO) is to train a neural network (NN) whose output gives a problem solution by directly optimizing the CO objective. Albeit with some advantages over traditional solvers, the current framework optimizes an averaged performance over the distribution of historical problem instances, which misaligns with the actual goal of CO that looks for a good solution to every future encountered instance. With this observation, we propose a new objective of unsupervised learning for CO where the goal of learning is to search for good initialization for future problem instances rather than give direct solutions. We propose a meta-learning-based training pipeline for this new objective. Our method achieves good empirical performance. We observe that even just the initial solution given by our model before fine-tuning can significantly outperform the baselines under various evaluation settings including evaluation across multiple datasets, and the case with big shifts in the problem scale. The reason we conjecture is that meta-learning-based training lets the model be loosely tied to each local optima for a training instance while being more adaptive to the changes of optimization landscapes across instances.