Reheated Gradient-based Discrete Sampling for Combinatorial Optimization

• URL: http://arxiv.org/abs/2503.04047v1
• Date: Thu, 06 Mar 2025 03:01:25 GMT
• Title: Reheated Gradient-based Discrete Sampling for Combinatorial Optimization
• Authors: Muheng Li, Ruqi Zhang,
• Abstract summary: gradient-based discrete sampling has emerged as a highly efficient, general-purpose solver for various optimization (CO) problems.<n>We introduce a novel reheating mechanism inspired by the concept of critical temperature and specific heat in physics, aimed at overcoming this limitation.
• Score: 12.572876283514095
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, gradient-based discrete sampling has emerged as a highly efficient, general-purpose solver for various combinatorial optimization (CO) problems, achieving performance comparable to or surpassing the popular data-driven approaches. However, we identify a critical issue in these methods, which we term ''wandering in contours''. This behavior refers to sampling new different solutions that share very similar objective values for a long time, leading to computational inefficiency and suboptimal exploration of potential solutions. In this paper, we introduce a novel reheating mechanism inspired by the concept of critical temperature and specific heat in physics, aimed at overcoming this limitation. Empirically, our method demonstrates superiority over existing sampling-based and data-driven algorithms across a diverse array of CO problems.

Related papers

• Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems [0.5156484100374059]
  We explore the relationship between recent line search approaches for deep optimization in the overparametrized regime and momentum directions. We introduce algorithmic that exploits a mix of data persistency, conjugateient type rules for the definition of the momentum parameter. The resulting algorithm is empirically shown to outperform other popular methods.
  arXiv  Detail & Related papers  (2024-11-11T16:26:33Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA) Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers.
  arXiv  Detail & Related papers  (2024-09-02T12:55:27Z)
• Structure-inspired Ansatz and Warm Start of Variational Quantum Algorithms for Quadratic Unconstrained Binary Optimization Problems [0.18874331450711404]
  This paper introduces a structure-inspired ansatz for addressing quadratic unconstrained binary optimization problems with the Variational Quantum Eigensolver. We propose a novel warm start technique that is based on imaginary time evolution. We demonstrate that this warm start method significantly improves the success rate and reduces the number of iterations required for the convergence of Variational Quantum Eigensolver.
  arXiv  Detail & Related papers  (2024-07-02T18:00:05Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• Sampling with Mollified Interaction Energy Descent [57.00583139477843]
  We present a new optimization-based method for sampling called mollified interaction energy descent (MIED) MIED minimizes a new class of energies on probability measures called mollified interaction energies (MIEs) We show experimentally that for unconstrained sampling problems our algorithm performs on par with existing particle-based algorithms like SVGD.
  arXiv  Detail & Related papers  (2022-10-24T16:54:18Z)
• The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
  Un differentiation approximates the solution using an iterative solver and differentiates it through the computational path. We show that we can either 1) choose a large learning rate leading to a fast convergence but accept that the algorithm may have an arbitrarily long burn-in phase or 2) choose a smaller learning rate leading to an immediate but slower convergence.
  arXiv  Detail & Related papers  (2022-09-27T09:27:29Z)
• Stochastic Gradient Methods with Preconditioned Updates [47.23741709751474]
  There are several algorithms for such problems, but existing methods often work poorly when badly scaled and/or ill-conditioned. Here we include preconditionimater based on Hutchinson's approach to approxing the diagonal Hessian. We prove convergence both when smoothness and the PL condition are assumed.
  arXiv  Detail & Related papers  (2022-06-01T07:38:08Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization [4.970364068620608]
  We exploit convexity and L-smoothness to improve the noisy estimates outputted by the gradient oracle. We show that increasing the number and proximity of the queried points leads to better gradient estimates. We also apply COCO in vanilla settings by plugging it in existing algorithms, such as SGD, Adam or STRSAGA.
  arXiv  Detail & Related papers  (2021-09-07T17:21:09Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21:20Z)

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.