Local-Minima-Preserving Polynomial Relaxation of Ising Problems

Debraj Banerjee, Santanu Mahapatra, Kunal N. Chaudhury
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:6172-6193, 2026.

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 local 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 scalable gradient-based optimizers such as ADAM. We demonstrate that our method achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-banerjee26a, title = {Local-Minima-Preserving Polynomial Relaxation of Ising Problems}, author = {Banerjee, Debraj and Mahapatra, Santanu and Chaudhury, Kunal N.}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {6172--6193}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/banerjee26a/banerjee26a.pdf}, url = {https://proceedings.mlr.press/v306/banerjee26a.html}, 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 local 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 scalable gradient-based optimizers such as ADAM. We demonstrate that our method achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.} }
Endnote
%0 Conference Paper %T Local-Minima-Preserving Polynomial Relaxation of Ising Problems %A Debraj Banerjee %A Santanu Mahapatra %A Kunal N. Chaudhury %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-banerjee26a %I PMLR %P 6172--6193 %U https://proceedings.mlr.press/v306/banerjee26a.html %V 306 %X 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 local 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 scalable gradient-based optimizers such as ADAM. We demonstrate that our method achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.
APA
Banerjee, D., Mahapatra, S. & Chaudhury, K.N.. (2026). Local-Minima-Preserving Polynomial Relaxation of Ising Problems. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:6172-6193 Available from https://proceedings.mlr.press/v306/banerjee26a.html.

Related Material