Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization

• URL: http://arxiv.org/abs/2502.02941v1
• Date: Wed, 05 Feb 2025 07:13:43 GMT
• Title: Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization
• Authors: Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, Junchi Yan,
• Abstract summary: We propose to learn direct mappings from different noise levels to the optimal solution for a given instance, facilitating high-quality generation with minimal shots. This is achieved through an optimization consistency training protocol, which minimizes the difference among samples. Experiments on two popular tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), demonstrate the superiority of Fast T2T regarding both solution quality and efficiency.
• Score: 83.65278205301576
• License:
• Abstract: Diffusion models have recently advanced Combinatorial Optimization (CO) as a powerful backbone for neural solvers. However, their iterative sampling process requiring denoising across multiple noise levels incurs substantial overhead. We propose to learn direct mappings from different noise levels to the optimal solution for a given instance, facilitating high-quality generation with minimal shots. This is achieved through an optimization consistency training protocol, which, for a given instance, minimizes the difference among samples originating from varying generative trajectories and time steps relative to the optimal solution. The proposed model enables fast single-step solution generation while retaining the option of multi-step sampling to trade for sampling quality, which offers a more effective and efficient alternative backbone for neural solvers. In addition, within the training-to-testing (T2T) framework, to bridge the gap between training on historical instances and solving new instances, we introduce a novel consistency-based gradient search scheme during the test stage, enabling more effective exploration of the solution space learned during training. It is achieved by updating the latent solution probabilities under objective gradient guidance during the alternation of noise injection and denoising steps. We refer to this model as Fast T2T. Extensive experiments on two popular tasks, the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), demonstrate the superiority of Fast T2T regarding both solution quality and efficiency, even outperforming LKH given limited time budgets. Notably, Fast T2T with merely one-step generation and one-step gradient search can mostly outperform the SOTA diffusion-based counterparts that require hundreds of steps, while achieving tens of times speedup.

Related papers

• A First-order Generative Bilevel Optimization Framework for Diffusion Models [57.40597004445473]
  Diffusion models iteratively denoise data samples to synthesize high-quality outputs. Traditional bilevel methods fail due to infinite-dimensional probability space and prohibitive sampling costs. We formalize this challenge as a generative bilevel optimization problem. Our first-order bilevel framework overcomes the incompatibility of conventional bilevel methods with diffusion processes.
  arXiv  Detail & Related papers  (2025-02-12T21:44:06Z)
• An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem [21.948190231334088]
  We propose DEITSP, a diffusion model with efficient iterations tailored for Traveling Salesman Problems. We introduce a one-step diffusion model that integrates the controlled discrete noise addition process with self-consistency enhancement. We also design a dual-modality graph transformer to bolster the extraction and fusion of features from node and edge modalities.
  arXiv  Detail & Related papers  (2025-01-23T15:47:04Z)
• Preventing Local Pitfalls in Vector Quantization via Optimal Transport [77.15924044466976]
  We introduce OptVQ, a novel vector quantization method that employs the Sinkhorn algorithm to optimize the optimal transport problem. Our experiments on image reconstruction tasks demonstrate that OptVQ achieves 100% codebook utilization and surpasses current state-of-the-art VQNs in reconstruction quality.
  arXiv  Detail & Related papers  (2024-12-19T18:58:14Z)
• DITTO-2: Distilled Diffusion Inference-Time T-Optimization for Music Generation [43.61383132919089]
  Controllable music generation methods are critical for human-centered AI-based music creation. We propose Distilled Diffusion Inference-Time T -Optimization (or DITTO-2), a new method to speed up inference-time optimization-based control.
  arXiv  Detail & Related papers  (2024-05-30T17:40:11Z)
• SinSR: Diffusion-Based Image Super-Resolution in a Single Step [119.18813219518042]
  Super-resolution (SR) methods based on diffusion models exhibit promising results. But their practical application is hindered by the substantial number of required inference steps. We propose a simple yet effective method for achieving single-step SR generation, named SinSR.
  arXiv  Detail & Related papers  (2023-11-23T16:21:29Z)
• Training Aware Sigmoidal Optimizer [2.99368851209995]
  Training Aware Sigmoidal functions present landscapes with much more saddle loss than local minima. We proposed the Training Aware Sigmoidal functions (TASO), which consists of a two-phases automated learning rate schedule. We compared the proposed approach with commonly used adaptive learning rate schedules such as Adam, RMS, and Adagrad.
  arXiv  Detail & Related papers  (2021-02-17T12:00:46Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Robust Learning Rate Selection for Stochastic Optimization via Splitting Diagnostic [5.395127324484869]
  SplitSGD is a new dynamic learning schedule for optimization. The method decreases the learning rate for better adaptation to the local geometry of the objective function. It essentially does not incur additional computational cost than standard SGD.
  arXiv  Detail & Related papers  (2019-10-18T19:38:53Z)

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.