CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization

• URL: http://arxiv.org/abs/2602.08210v1
• Date: Mon, 09 Feb 2026 02:19:30 GMT
• Title: CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization
• Abstract summary: Heatmap-based solvers have emerged as a promising paradigm for Combinatorial Optimization (CO)<n>We argue that the dominant Supervised Learning (SL) training paradigm suffers from a fundamental objective mismatch.<n>We propose CADO, a framework that formulates the diffusion denoising process as an MDP to directly optimize the post-decoded solution cost.
• Score: 8.485234027066012
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Heatmap-based solvers have emerged as a promising paradigm for Combinatorial Optimization (CO). However, we argue that the dominant Supervised Learning (SL) training paradigm suffers from a fundamental objective mismatch: minimizing imitation loss (e.g., cross-entropy) does not guarantee solution cost minimization. We dissect this mismatch into two deficiencies: Decoder-Blindness (being oblivious to the non-differentiable decoding process) and Cost-Blindness (prioritizing structural imitation over solution quality). We empirically demonstrate that these intrinsic flaws impose a hard performance ceiling. To overcome this limitation, we propose CADO (Cost-Aware Diffusion models for Optimization), a streamlined Reinforcement Learning fine-tuning framework that formulates the diffusion denoising process as an MDP to directly optimize the post-decoded solution cost. We introduce Label-Centered Reward, which repurposes ground-truth labels as unbiased baselines rather than imitation targets, and Hybrid Fine-Tuning for parameter-efficient adaptation. CADO achieves state-of-the-art performance across diverse benchmarks, validating that objective alignment is essential for unlocking the full potential of heatmap-based solvers.

Related papers

• A Robust Optimization Approach to Sparse Principal Component Analysis [8.963365635440722]
  We propose Adversarial PCA (AdvPCA), which leverages robust optimization to achieve sparsity.<n>We show that this formulation admits a closed-form reduction, leading to a practical iterative algorithm.<n>By theoretically characterizing the solution, we derive a data-adaptive parameterization that allows the algorithm to perform effectively out of the box.
  arXiv  Detail & Related papers  (2026-06-02T12:14:12Z)
• Reward Score Matching: Unifying Reward-based Fine-tuning for Flow and Diffusion Models [54.597200388738656]
  Reward-based fine-tuning aims to steer a pretrained diffusion or flow-based generative model toward higher-reward samples.<n>We show that many can be written under a common framework, which we call reward score matching (RSM)
  arXiv  Detail & Related papers  (2026-04-19T12:47:52Z)
• LFPO: Likelihood-Free Policy Optimization for Masked Diffusion Models [48.68246945083386]
  Likelihood-Free Policy Optimization (LFPO) is a native framework that maps the concept of vector field flow matching to the discrete token space.<n>LFPO formulates alignment as geometric velocity rectification, which directly optimize denoising logits via contrastive updates.<n>Experiments demonstrate that LFPO not only outperforms state-of-the-art baselines on code and reasoning benchmarks but also accelerates inference by approximately 20% through reduced diffusion steps.
  arXiv  Detail & Related papers  (2026-03-02T07:42:55Z)
• Parallel Diffusion Solver via Residual Dirichlet Policy Optimization [88.7827307535107]
  Diffusion models (DMs) have achieved state-of-the-art generative performance but suffer from high sampling latency due to their sequential denoising nature.<n>Existing solver-based acceleration methods often face significant image quality degradation under a low-dimensional budget.<n>We propose the Ensemble Parallel Direction solver (dubbed as EPD-EPr), a novel ODE solver that mitigates these errors by incorporating multiple gradient parallel evaluations in each step.
  arXiv  Detail & Related papers  (2025-12-28T05:48:55Z)
• Efficient Utility-Preserving Machine Unlearning with Implicit Gradient Surgery [30.346382763036598]
  Machine unlearning (MU) aims to efficiently remove sensitive or harmful memory from a pre-trained model.<n>The key challenge is to balance the potential tradeoff between unlearning efficacy and utility preservation.<n>We propose an implicit gradient surgery method, which approximates the solution to a constrained optimization problem via only one backpropagation.
  arXiv  Detail & Related papers  (2025-10-25T02:49:26Z)
• Optimization Modeling via Semantic Anchored Alignment [30.047608671041104]
  We propose SAC-Opt, a backward-guided correction framework that grounds optimization modeling in problem semantics rather than solver feedback.<n>At each step, SAC-Opt aligns the original semantic anchors with those reconstructed from the generated code and selectively corrects only the mismatched components.<n> Empirical results on seven public datasets demonstrate that SAC-Opt improves average modeling accuracy by 7.8%, with gains of up to 21.9% on the ComplexLP dataset.
  arXiv  Detail & Related papers  (2025-09-28T12:25:31Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [9.788112471288057]
  We study the computation of the rate-distortion-perception function (RDPF) for discrete memoryless sources.<n>We characterize optimal parametric solutions for the convex programming problem.<n>We show, by deriving necessary and sufficient conditions, that both schemes guarantee a globally optimal solution.
  arXiv  Detail & Related papers  (2024-08-27T12:50:12Z)
• Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization [78.82586283794886]
  $chi2$-Preference Optimization ($chi$PO) is an efficient offline alignment algorithm provably robust to overoptimization.<n>$chi$PO implements the principle of pessimism in the face of uncertainty via regularization.<n>$chi$PO's simplicity and strong guarantees make it the first practical and general-purpose offline alignment algorithm provably robust to overoptimization.
  arXiv  Detail & Related papers  (2024-07-18T11:08:40Z)
• Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
  We identify the source of misalignment as a form of distributional shift and uncertainty in learning human preferences.<n>To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model.<n>Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines a preference optimization loss and a supervised learning loss.
  arXiv  Detail & Related papers  (2024-05-26T05:38:50Z)
• Conflict-Averse Gradient Optimization of Ensembles for Effective Offline Model-Based Optimization [0.0]
  We evaluate two algorithms for combining gradient information: multiple gradient descent algorithm (MGDA) and conflict-averse gradient descent (CAGrad) Our results suggest that MGDA and CAGrad strike a desirable balance between conservatism and optimality and can help robustify data-driven offline MBO without compromising optimality of designs.
  arXiv  Detail & Related papers  (2023-03-31T10:00:27Z)
• Joint inference and input optimization in equilibrium networks [68.63726855991052]
  deep equilibrium model is a class of models that foregoes traditional network depth and instead computes the output of a network by finding the fixed point of a single nonlinear layer. We show that there is a natural synergy between these two settings. We demonstrate this strategy on various tasks such as training generative models while optimizing over latent codes, training models for inverse problems like denoising and inpainting, adversarial training and gradient based meta-learning.
  arXiv  Detail & Related papers  (2021-11-25T19:59:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.