提出TACO框架,让模型在测试时高效自适应优化,兼顾泛化与个性调整。
Test-Time Adaptation for Unsupervised Combinatorial Optimization
- 用策略性热启动修复通用模型在测试时的适应缺陷
- 在4类经典问题上均优于直接微调或从头优化
- 适合需要快速高精度求解的动态组合优化场景
无监督神经组合优化(NCO)可在无真值解的情况下学习强大求解器。现有方法分为两类:一类是面向跨实例泛化的模型,推理效率高但缺乏实例级适应能力;另一类是测试时独立优化的实例专属模型,灵活但难以利用学习到的归纳偏置且易陷入局部最优。本文提出统一两者的模型无关测试时自适应框架TACO,通过战略性地放松训练参数以保留归纳偏置,实现快速有效的无监督适应。相比直接微调通用模型或从头优化实例模型,TACO在最小顶点覆盖、最大团、最大独立集和最大割等经典问题上均取得更优解质量,计算开销几乎不变。实验验证了其在静态、分布漂移及动态问题上的有效性与鲁棒性,成为连接泛化型与实例型无监督NCO的实用桥梁。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。