Abstract:Unsupervised neural combinatorial optimization (NCO) enables learning powerful solvers without access to ground-truth solutions. Existing approaches fall into two disjoint paradigms: models trained for generalization across instances, and instance-specific models optimized independently at test time. While the former are efficient during inference, they lack effective instance-wise adaptability; the latter are flexible but fail to exploit learned inductive structure and are prone to poor local optima. This motivates the central question of our work: how can we leverage the inductive bias learned through generalization while unlocking the flexibility required for effective instance-wise adaptation? We first identify a challenge in bridging these two paradigms: generalization-focused models often constitute poor warm starts for instance-wise optimization, potentially underperforming even randomly initialized models when fine-tuned at test time. To resolve this incompatibility, we propose TACO, a model-agnostic test-time adaptation framework that unifies and extends the two existing paradigms for unsupervised NCO. TACO applies strategic warm-starting to partially relax trained parameters while preserving inductive bias, enabling rapid and effective unsupervised adaptation. Crucially, compared to naively fine-tuning a trained generalizable model or optimizing an instance-specific model from scratch, TACO achieves better solution quality while incurring negligible additional computational cost. Experiments on the canonical problems of minimum vertex cover, maximum clique, maximum independent set, and max cut demonstrate the effectiveness and robustness of TACO across static, distribution-shifted, and dynamic combinatorial optimization problems, establishing it as a practical bridge between generalizable and instance-specific unsupervised NCO.
| Comments: | TMLR 2026 |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2601.21048 [cs.LG] |
| (or arXiv:2601.21048v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2601.21048 arXiv-issued DOI via DataCite |
From: Yiqiao Liao [view email]
[v1]
Wed, 28 Jan 2026 21:14:39 UTC (79 KB)
[v2]
Sun, 26 Apr 2026 02:35:03 UTC (96 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。