A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization
math.OC, quant-ph
Submitted: 2025-10-20
Updated: 2026-10-29
Comments: 21 pages, 7 figures, 1 table
DOI: 10.21203/rs.3.rs-9886419/v1
Code: https://github.com/baptistechev/troma
License: http://creativecommons.org/licenses/by/4.0/
The gist: In this paper, we present a Monte-Carlo Compressive Optimization algorithm, a new method for black-box combinatorial optimization, which only assumes that the objective is compressible.
Terminology
Abstract
In this paper, we present a Monte-Carlo Compressive Optimization algorithm, a new method for black-box combinatorial optimization, which only assumes that the objective is compressible. The method relies on random queries to the objective function in order to estimate generalized moments. Next, a greedy algorithm from compressive sensing is repurposed to find the global optimum when not overfitting to the samples. We provide numerical results giving evidence that our method is competitive by comparing it with digital annealing. Moreover, we give theoretical justification for the success of the algorithm and analyze its properties. The practicality of our algorithm is enhanced by the ability to tune the heuristic parameters to the available computational resources. An end-to-end open-source implementation is available to use our method.
Sources
- Ising formulations of many NP problems
- Quantum annealing: An introduction and new developments
- Compressive Statistical Learning with Random Feature Moments
- NP-complete Problems and Physical Reality
- A Quantum Approximate Optimization Algorithm
- Initialization Method for Factorization Machine Based on Low-Rank Approximation for Constructing a Corrected Approximate Ising Model
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise