Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization

• URL: http://arxiv.org/abs/2510.19544v1
• Date: Wed, 22 Oct 2025 12:50:27 GMT
• Title: Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization
• Abstract summary: We use a Global Annealing Monte Carlo algorithm that integrates standard local moves with global moves proposed via machine learning.<n>We show that local moves play a crucial role in achieving optimal performance.<n>These results provide the first clear and robust evidence that a machine learning-assisted optimization method can exceed the capabilities of classical state-of-the-art techniques.
• Score: 0.38233569758620045
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization problems are central to both practical applications and the development of optimization methods. While classical and quantum algorithms have been refined over decades, machine learning-assisted approaches are comparatively recent and have not yet consistently outperformed simple, state-of-the-art classical methods. Here, we focus on a class of Quadratic Unconstrained Binary Optimization (QUBO) problems, specifically the challenge of finding minimum energy configurations in three-dimensional Ising spin glasses. We use a Global Annealing Monte Carlo algorithm that integrates standard local moves with global moves proposed via machine learning. We show that local moves play a crucial role in achieving optimal performance. Benchmarking against Simulated Annealing and Population Annealing, we demonstrate that Global Annealing not only surpasses the performance of Simulated Annealing but also exhibits greater robustness than Population Annealing, maintaining effectiveness across problem hardness and system size without hyperparameter tuning. These results provide, to our knowledge, the first clear and robust evidence that a machine learning-assisted optimization method can exceed the capabilities of classical state-of-the-art techniques in a combinatorial optimization setting.

Related papers

• Bayesian Optimization in Linear Time [1.6500749121196987]
  We show that our method achieves superior optimization performance in all tests.<n>We adapt both the modeling and acquisitive aspects of standard Bayesian optimization to work harmoniously with the partitioning scheme.
  arXiv  Detail & Related papers  (2026-04-30T21:16:12Z)
• Integrating Multi-Armed Bandit, Active Learning, and Distributed Computing for Scalable Optimization [0.0]
  ALMAB-DC is a unified framework for scalable black-box optimization.<n>It integrates active learning, multi-armed bandits, and distributed computing.<n>It consistently outperforms state-of-the-art black-box evaluations.
  arXiv  Detail & Related papers  (2026-01-02T09:06:56Z)
• L-SR1: Learned Symmetric-Rank-One Preconditioning [5.421390145168128]
  End-to-end deep learning has achieved impressive results but remains limited by its reliance on large labeled datasets.<n>In contrast, classical optimization methods are data-efficient and lightweight but often suffer from slow convergence.<n>We propose a novel learned second-order vectors that introduces a trainable preconditioning unit to enhance the classical Symmetric-Rank-One algorithm.
  arXiv  Detail & Related papers  (2025-08-17T07:37:29Z)
• A Survey on Inference Optimization Techniques for Mixture of Experts Models [50.40325411764262]
  Large-scale Mixture of Experts (MoE) models offer enhanced model capacity and computational efficiency through conditional computation.<n> deploying and running inference on these models presents significant challenges in computational resources, latency, and energy efficiency.<n>This survey analyzes optimization techniques for MoE models across the entire system stack.
  arXiv  Detail & Related papers  (2024-12-18T14:11:15Z)
• LLM as a Complementary Optimizer to Gradient Descent: A Case Study in Prompt Tuning [69.95292905263393]
  We show that gradient-based and high-level LLMs can effectively collaborate a combined optimization framework.<n>In this paper, we show that these complementary to each other and can effectively collaborate a combined optimization framework.
  arXiv  Detail & Related papers  (2024-05-30T06:24:14Z)
• Localized Zeroth-Order Prompt Optimization [54.964765668688806]
  We propose a novel algorithm, namely localized zeroth-order prompt optimization (ZOPO) ZOPO incorporates a Neural Tangent Kernel-based derived Gaussian process into standard zeroth-order optimization for an efficient search of well-performing local optima in prompt optimization. Remarkably, ZOPO outperforms existing baselines in terms of both the optimization performance and the query efficiency.
  arXiv  Detail & Related papers  (2024-03-05T14:18:15Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  We present a comprehensive study on the integration of machine learning (ML) techniques into Huawei Cloud's OptVerse AI solver. We showcase our methods for generating complex SAT and MILP instances utilizing generative models that mirror multifaceted structures of real-world problem. We detail the incorporation of state-of-the-art parameter tuning algorithms which markedly elevate solver performance.
  arXiv  Detail & Related papers  (2024-01-11T15:02:15Z)
• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  We introduce contextual bilevel optimization (CSBO) -- a bilevel optimization framework with the lower-level problem minimizing an expectation on some contextual information and the upper-level variable. It is important for applications such as meta-learning, personalized learning, end-to-end learning, and Wasserstein distributionally robustly optimization with side information (WDRO-SI)
  arXiv  Detail & Related papers  (2023-10-27T23:24:37Z)
• Landscape-Sketch-Step: An AI/ML-Based Metaheuristic for Surrogate Optimization Problems [0.0]
  We introduce a newimats for global optimization in scenarios where extensive evaluations of the cost function are expensive, inaccessible, or even prohibitive. The method, which we call Landscape-Sketch-and-Step (LSS), combines Machine Learning, Replica Optimization, and Reinforcement Learning techniques.
  arXiv  Detail & Related papers  (2023-09-14T01:53:45Z)
• Large-Batch, Iteration-Efficient Neural Bayesian Design Optimization [37.339567743948955]
  We present a novel Bayesian optimization framework specifically tailored to address the limitations of BO. Our key contribution is a highly scalable, sample-based acquisition function that performs a non-dominated sorting of objectives. We show that our acquisition function in combination with different Bayesian neural network surrogates is effective in data-intensive environments with a minimal number of iterations.
  arXiv  Detail & Related papers  (2023-06-01T19:10:57Z)
• Quantum approximate optimization via learning-based adaptive optimization [5.399532145408153]
  Quantum approximate optimization algorithm (QAOA) is designed to solve objective optimization problems. Our results demonstrate that the algorithm greatly outperforms conventional approximations in terms of speed, accuracy, efficiency and stability. This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks.
  arXiv  Detail & Related papers  (2023-03-27T02:14:56Z)
• Application of Monte Carlo Stochastic Optimization (MOST) to Deep Learning [0.0]
  In this paper, we apply the Monte Carlo optimization (MOST) proposed by the authors to a deep learning of XOR gate. As a result, it was confirmed that it converged faster than the existing method.
  arXiv  Detail & Related papers  (2021-09-02T05:52:26Z)
• Meta-Learning with Neural Tangent Kernels [58.06951624702086]
  We propose the first meta-learning paradigm in the Reproducing Kernel Hilbert Space (RKHS) induced by the meta-model's Neural Tangent Kernel (NTK) Within this paradigm, we introduce two meta-learning algorithms, which no longer need a sub-optimal iterative inner-loop adaptation as in the MAML framework. We achieve this goal by 1) replacing the adaptation with a fast-adaptive regularizer in the RKHS; and 2) solving the adaptation analytically based on the NTK theory.
  arXiv  Detail & Related papers  (2021-02-07T20:53:23Z)

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.