On Training-Test (Mis)alignment in Unsupervised Combinatorial Optimization: Observation, Empirical Exploration, and Analysis
Fanchen Bu, Kijung Shin · 2025
Read On Training-Test (Mis)alignment in Unsupervised Combinatorial Optimization: Observation, Empirical Exploration, and Analysis by Fanchen Bu, Kijung Shin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16732.txt.
Introduction
Fanchen Bu and Kijung Shin exposed a quiet mismatch in how neural solvers for hard combinatorial problems are trained and used. In unsupervised combinatorial optimization, training rewards soft, probabilistic choices that point toward good answers. At test time a derandomization step hardens those choices into final answers. The two stages were designed separately, and the authors noticed lower training loss does not always mean better final answers, even on the training data itself.
They demonstrate the failure cases, then test a repair: fold a smooth, differentiable stand-in for derandomization into training, so the model learns with the end step in view. Alignment between training and testing improved. The authors are candid that the fix also makes training harder, and they frame the work as an opening analysis.
Catalog record
| CREATOR | Fanchen Bu, Kijung Shin |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 19 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-16732
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Training-Test (Mis)alignment in Unsupervised Combinatorial Optimization: Observation, Empirical Exploration, and Analysis Fanchen Bu, Kijung Shin Abstract In unsupervised combinatorial optimization (UCO), during training, one aims to have continuous decisions that are promising in a probabilistic sense for each training instance, which enables end-to-end training on initially discrete and non-differentiable problems. At the test time, for each test instance, starting from continuous decisions, derandomization is typically applied to obtain the final deterministic decisions. Researchers have developed more and more powerful test-time derandomization schemes to enhance the empirical performance and the theoretical guarantee of UCO methods. However, we notice a misalignment between training and testing in the existing UCO methods. Consequently, lower training losses do not necessarily entail better post-derandomization performance, even for the training instances without any data distribution shift . Empirically, we indeed observe such undesirable cases. We explore a preliminary idea to better align training and testing in UCO by including a differentiable version of derandomization into training. Our empirical exploration shows that such an idea indeed improves training-test alignment, but also introduces nontrivial challenges into training. 1 Introduction Combinatorial optimization (CO) problems are naturally discrete. Typical examples include optimization problems on graphs where we make binary yes-or-no decisions on each node, and the objective is a function of the graph structure and the binary decisions. CO problems have a rich lineage in various research fields, including theoretical computer science ( Arumugam et al. 2016 ) and operations research ( Modaresi et al. 2020 ) , with real-world applications from network design ( Cheng et al. 2006 ) to scheduling ( Hwang and Cheng 2001 ) and bioinformatics ( Bauer et al. 2007 ) . However, the discrete nature of CO problems makes it non-trivial to apply typical machine learning methods that are based on differentiable optimization to them. To overcome these challenges, researchers have explored various strategies to effectively combine machine learning with CO problems ( Bengio et al. 2021 ) . Early approaches often involved supervised methods ( Li et al. 2018 ) or reinforcement learning techniques ( Kool et al. 2019 ; Berto et al. 2025 ) . However, these methods require labeled data or extensive interaction, limiting their applicability and generalizability in many real-world scenarios ( Karalias and Loukas 2020 ) . Consequently, the field has seen a growing interest in unsupervised approaches, resulting in the development of unsupervised combinatorial optimization (UCO) methods. The key idea of UCO is to (1) allow continuous decisions and (2) evaluate the expected objective by interpreting the continuous decisions as random variables, which gives a fully differentiable process and enables end-to-end training. At the test time, derandomization is typically applied to continuous decisions to transform them into deterministic decisions as the final output ( Karalias and Loukas 2020 ) . Over the course of time, UCO researchers have developed more and more powerful test-time derandomization schemes, from naive random sampling ( Karalias and Loukas 2020 ) , iterative rounding ( Karalias and Loukas 2020 ; Wang et al. 2022 ) , to greedy derandomization ( Bu et al. 2024 ) . With the development of test-time derandomization, we have witnessed the enhancement of the empirical performance as well as the theoretical quality guarantee of UCO methods. However, we notice a misalignment between training and testing in the existing UCO methods: the training essentially tries to optimize the expected quality of the output continuous decisions assuming naive random sampling, while rather sophisticated derandomization is actually used at the test time. Therefore, even if we have lower training losses, we cannot guarantee better post-derandomization performance at the test time, even for the training instances (i.e., here we are not discussing the training-test misalignment regarding data distributions but regarding methodology). We indeed empirically observe such undesirable cases. We explore a preliminary idea to better align training and testing in UCO by including a differentiable version of derandomization into training. By our empirical exploration, we validate that such an idea indeed can improve training-test alignment. However, we also observe that including such additional soft derandomization schemes into training increases the difficulty of training, i.e., we may not be able to have the training losses stably decrease during training. Our analysis suggests that the future development of UCO methods may need to find a balance between training-test alignment and the ease of training. Reproducibility. The code and datasets are available in the online appendix ( Bu and Shin 2025 ) . 1 1 1 https://github.com/bokveizen/uco_derand Algorithm 1 Iterative Rounding 1: (1) Continuous decisions \tilde{D}\in[0,1]^{n} , (2) Rounding sequence \pi_{n}=(v_{1},\dots,v_{n}) 2: Final discrete decisions D\in\{0,1\}^{n} 3: D\leftarrow\tilde{D} \triangleright Initialization 4: for j\leftarrow v_{1}\,\mathbf{to}\,v_{n} do \triangleright Iteration following the sequence 5: for b\in\{0,1\} do 6: D^{\prime}\leftarrow D \triangleright Copy 7: D^{\prime}_{j}\leftarrow b \triangleright Modify a single entry 8: \Delta_{b}\leftarrow\tilde{f}(D)-\tilde{f}(D^{\prime}) \triangleright Evaluation 9: end for 10: D_{j}\leftarrow\arg\max_{b\in\{0,1\}}\Delta_{b} \triangleright Rounding 11: end for 12: return D 2 Preliminaries and Background 2.1 Combinatorial Optimization (CO) We consider CO problems with n binary decisions, where n is a positive integer. A CO problem aims to find the optimal decisions D_{\textrm{opt}} inside a feasible set \mathcal{C} such that D_{\textrm{opt}}\in\mathcal{C}\subseteq\{0,1\}^{n} , to minimize an objective f:\mathcal{C}\mapsto\mathbb{R} (i.e., D_{\textrm{opt}}=\arg\min_{D\in\mathcal{C}}f(D) ). 2.2 Unsupervised Combinatorial Optimization (UCO) Based on the probabilistic method ( Erdős and Spencer 1974 ) , Karalias and Loukas 2020 proposed the UCO framework with the high-level idea to (1) apply continuous relaxation to the objective f and its domain, to obtain \tilde{f}:[0,1]^{n}\to\mathbb{R} and enable end-to-end training, and (2) apply derandomization at the test time to obtain the final output decisions D_{\mathrm{out}}\in\mathcal{C} . Continuous relaxation. Each \tilde{D}\in[0,1]^{n} is interpreted as a distribution (typically, an independent multivariate Bernoulli distribution) on \{0,1\}^{n} , and we aim to construct a differentiable \tilde{f} such that \tilde{f}(\tilde{D})\approx\mathbb{E}_{D\sim\tilde{D}}[f(D)]+\beta\Pr_{D\sim\tilde{D}}[D\notin\mathcal{C}] with constraint coefficient \beta>0 . The key points are (1) now we are able to conduct end-to-end training with this differentiable surrogate \tilde{f} instead of the originally discrete non-differentiable f , and (2) when \tilde{f} is minimized, it is guaranteed that the optimal \tilde{D}_{\mathrm{opt}}=\arg\min_{\tilde{D}\in[0,1]^{n}}\tilde{f}(\tilde{D}) corresponds to the optimal {D}_{\mathrm{opt}} for the original objective f . Algorithm 2 Greedy Rounding 1: Continuous decisions \tilde{D}\in[0,1]^{n} 2: Final discrete decisions D\in\{0,1\}^{n} 3: D\leftarrow\tilde{D} \triangleright Initialization 4: repeat 5: for j\in\{1,\dots,n\} and b\in\{0,1\} do 6: D^{\prime}\leftarrow D \triangleright Copy 7: D^{\prime}_{j}\leftarrow b \triangleright Modify a single entry 8: \Delta_{j,b}\leftarrow\tilde{f}(D)-\tilde{f}(D^{\prime}) \triangleright Evaluation 9: end for 10: (j^{*},b^{*})\leftarrow\arg\max_{j,b\in[n]\times\{0,1\}}\Delta_{j,b} \triangleright Best choice 11: D_{j^{*}}\leftarrow b^{*} \triangleright Rounding with the best choice 12: until \Delta_{j^{*},b^{*}}\leq 0 \triangleright Until local minimum 13: return D Derandomization. At the test time, for each test instance, derandomization is used to obtain the final output discrete decisions. Researchers have considered various derandomization schemes for UCO, including (let \tilde{D}_{\mathrm{output}}\in[0,1]^{n} be the initial continuous output for the test instance): • Naive random sampling ( Karalias and Loukas 2020 ) : We sample D_{\mathrm{out}} from the distribution represented by \tilde{D}_{\mathrm{output}} ; • Iterative rounding ( Karalias and Loukas 2020 ; Wang et al. 2022 ) : We fix a sequence \pi_{n}=\{v_{1},v_{2},\ldots,v_{n}\} , iterate for i=1,2,\ldots,n while rounding for v_{i} to the one between 0 and 1 that gives lower \tilde{f} , and obtain D_{\mathrm{out}} after rounding all the n entries (see Algorithm 1 ); • Greedy rounding ( Bu et al. 2024 ) : Repeatedly,