A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization

• URL: http://arxiv.org/abs/2510.24755v1
• Date: Mon, 20 Oct 2025 10:38:53 GMT
• Title: A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization
• Authors: Baptiste Chevalier, Shimpei Yamaguchi, Wojciech Roga, Masahiro Takeoka,
• Abstract summary: We present the Monte-Carlo Compressive Optimization algorithm, a new method to solve a optimization problem that is assumed compressible.<n>The practicality of our algorithm is enhanced by the ability to tune parameters to available computational resources.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we present the Monte-Carlo Compressive Optimization algorithm, a new method to solve a combinatorial optimization problem that is assumed 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 samples. We provide numerical results giving evidences that our methods overcome state-of-the-art dual annealing. Moreover, we also give theoretical justification of the algorithm success and analyze its properties. The practicality of our algorithm is enhanced by the ability to tune heuristic parameters to available computational resources.

Related papers

• Improving sample efficiency of high dimensional Bayesian optimization with MCMC [7.241485121318798]
  We propose a new method based on Markov Chain Monte Carlo to efficiently sample from an approximated posterior. We show experimentally that both the Metropolis-Hastings and the Langevin Dynamics version of our algorithm outperform state-of-the-art methods in high-dimensional sequential optimization and reinforcement learning benchmarks.
  arXiv  Detail & Related papers  (2024-01-05T05:56:42Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  We propose and analyse a family of generalised composite mirror descent algorithms. With adaptive step sizes, the proposed algorithms converge without requiring prior knowledge of the problem. We exploit the low-dimensional structure of the decision sets for high-dimensional problems.
  arXiv  Detail & Related papers  (2022-11-21T18:31:43Z)
• An Algebraically Converging Stochastic Gradient Descent Algorithm for Global Optimization [14.121491356732188]
  A key component in the algorithm is the randomness based on the value of the objective function.<n>We prove the convergence of the algorithm with an algebra and tuning in the parameter space.<n>We present several numerical examples to demonstrate the efficiency and robustness of the algorithm.
  arXiv  Detail & Related papers  (2022-04-12T16:27:49Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition [63.011641517977644]
  Our algorithm generates a sequence of finite-dimensional random subspaces of functional space spanned by a set of draws from the experimenter's Gaussian Process. Standard Bayesian optimisation is applied on each subspace, and the best solution found used as a starting point (origin) for the next subspace. We test our algorithm in simulated and real-world experiments, namely blind function matching, finding the optimal precipitation-strengthening function for an aluminium alloy, and learning rate schedule optimisation for deep networks.
  arXiv  Detail & Related papers  (2020-09-08T06:54:11Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

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.