Local-Minima-Preserving Continuous Relaxation of Ising Problems

• URL: http://arxiv.org/abs/2606.30333v1
• Date: Mon, 29 Jun 2026 14:13:56 GMT
• Title: Local-Minima-Preserving Continuous Relaxation of Ising Problems
• Abstract summary: We consider the notion of one-flip local minima for the Ising problem.<n>We show that there exists a one-to-one correspondence between the local minima of the relaxation and the one-flip minima of the original Ising problem.<n>This guarantee reduces the Ising problem to finding the local minima of a smooth function.
• Score: 11.357919122960732
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The generalized Ising problem captures a broad spectrum of hard combinatorial problems, including MAX-CUT, Number Partitioning (NPP), and Maximum Independent Set. In this work, we consider the notion of one-flip local minima for this problem. We construct a polynomial relaxation and prove the landscape equivalence theorem: there exists a one-to-one correspondence between the local minima of the relaxation and the one-flip minima of the original Ising problem. This guarantee reduces the Ising problem to finding the local minima of a smooth function, allowing us to leverage gradient-based optimizers such as ADAM. We demonstrate that our method is scalable and it achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.

Related papers

• Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe [61.68406997155879]
  State-of-the-art Large Language Model (LLM) pruning methods operate layer-wise, minimizing the per-layer pruning error on a small dataset to avoid full retraining.<n>Existing methods hence rely on greedy convexs that ignore the weight interactions in the pruning objective.<n>Our method drastically reduces the per-layer pruning error, outperforms strong baselines on state-of-the-art GPT architectures, and remains memory-efficient.
  arXiv  Detail & Related papers  (2025-10-15T16:13:44Z)
• A first-order method for constrained nonconvex--nonconcave minimax problems under a local Kurdyka-Łojasiewicz condition [5.834528275910258]
  We study a class of constrained non-nonconcave minimax problems in which the inner involves potentially complex constraints.<n>We show the maximal function of the original problem enjoys a local H"older property smoothness.<n>We propose a method for solving constrained optimization problems and establish its convergence under a local KL condition.
  arXiv  Detail & Related papers  (2025-10-01T17:54:27Z)
• A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Łojasiewicz condition [1.534667887016089]
  We study a class of non-nonconcave minimax problems in which the inner problem a local Kurdyka-Lojasiewicz (KL) condition varies with the outer minimization variable.<n>In particular, as an algorithm progresses toward a stationary point of the problem, the region over which the KL condition holds may shrink, resulting in a more potentially ill-conditioned landscape.
  arXiv  Detail & Related papers  (2025-07-02T17:45:10Z)
• Stochastic Optimization with Constraints: A Non-asymptotic Instance-Dependent Analysis [2.1756081703276]
  We analyze the behavior of a natural variance reduced proximal gradient (VRPG) algorithm for convex optimization under convex constraints. Our main result is a non-asymptotic guarantee for VRPG algorithm. We show that our guarantee captures the complexity of the loss function, the variability of the noise, and the geometry of the constraint set.
  arXiv  Detail & Related papers  (2024-03-24T14:45:11Z)
• Energy Landscapes for the Quantum Approximate Optimisation Algorithm [0.0]
  We use basin-hopping global methods to navigate the energy landscapes for QAOA ans"atze for various graphs. We find that the corresponding landscapes generally have a single funnel organisation, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities.
  arXiv  Detail & Related papers  (2024-01-09T19:17:01Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  We show that policies under study avoid strict saddle points / submanifolds with probability 1. This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
  arXiv  Detail & Related papers  (2023-11-04T11:12:24Z)
• Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization [50.10952609321302]
  compositional minimax optimization is a pivotal challenge across various machine learning domains. Current methods of compositional minimax optimization are plagued by sub-optimal complexities or heavy reliance on sizable batch sizes. This paper introduces a novel method, called Nested STOchastic Recursive Momentum (NSTORM), which can achieve the optimal sample complexity of $O(kappa3 /epsilon3 )$.
  arXiv  Detail & Related papers  (2023-08-18T14:57:21Z)
• Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems [46.71914490521821]
  This paper introduces a new extragradient-type algorithm for a class of non-nonconcave minimax problems. The proposed algorithm is applicable to constrained and regularized problems.
  arXiv  Detail & Related papers  (2023-02-20T08:37:08Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  The minimax algorithms for neural networks have been developed to solve many problems. In this paper, we propose two types of minimax algorithms. For the setting, we propose DRSGDA and prove that our method achieves a gradient.
  arXiv  Detail & Related papers  (2023-02-08T01:42:45Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)

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.