Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization

• URL: http://arxiv.org/abs/2410.23270v1
• Date: Wed, 30 Oct 2024 17:52:56 GMT
• Title: Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization
• Authors: Shouvanik Chakrabarti, Dylan Herman, Guneykan Ozgul, Shuchen Zhu, Brandon Augustino, Tianyi Hao, Zichang He, Ruslan Shaydulin, Marco Pistoia,
• Abstract summary: We analyze generalizations of algorithms based on the short-path framework first proposed by Hastings. Under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups. We conclude the paper with a numerical analysis that guides the choice of parameters for short path algorithms.
• Score: 3.3508820106803796
• License:
• Abstract: We analyze generalizations of algorithms based on the short-path framework first proposed by Hastings [Quantum 2, 78 (2018)], which has been extended and shown by Dalzell et al. [STOC '22] to achieve super-Grover speedups for certain binary optimization problems. We demonstrate that, under some commonly satisfied technical conditions, an appropriate generalization can achieve super-quadratic speedups not only over unstructured search but also over a classical optimization algorithm that searches for the optimum by drawing samples from the stationary distribution of a Markov Chain. We employ this framework to obtain algorithms for problems including variants of Max-Bisection, Max Independent Set, the Ising Model, and the Sherrington Kirkpatrick Model, whose runtimes are asymptotically faster than those obtainable from previous short path techniques. For random regular graphs of sufficiently high degree, our algorithm is super-quadratically faster than the best rigorously proven classical runtimes for regular graphs. Our results also shed light on the quantum nature of short path algorithms, by identifying a setting where our algorithm is super-quadratically faster than any polynomial time Gibbs sampler, unless NP = RP. We conclude the paper with a numerical analysis that guides the choice of parameters for short path algorithms and raises the possibility of super-quadratic speedups in settings that are currently beyond our theoretical analysis.

Related papers

• 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)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Run Time Analysis for Random Local Search on Generalized Majority Functions [1.0965065178451106]
  We study how one of its properties -- neutrality -- influences the run time of random local search. We provide a theorem, applicable to many optimization algorithms, that links the run time of MAJORITY with its symmetric version HASMAJORITY.
  arXiv  Detail & Related papers  (2022-04-27T08:40:33Z)
• Fast optimal structures generator for parameterized quantum circuits [4.655660925754175]
  Current structure optimization algorithms optimize the structure of quantum circuit from scratch for each new task of variational quantum algorithms (VQAs) We propose a rapid structure optimization algorithm for VQAs which automatically determines the number of quantum gates and directly generates the optimal structures for new tasks.
  arXiv  Detail & Related papers  (2022-01-10T12:19:37Z)
• Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path [29.289190242826688]
  We introduce a generic template for developing regret algorithms in the Shortest Path (SSP) model. We develop two new algorithms: the first is model-free and minimax optimal under strictly positive costs. Both algorithms admit highly sparse updates, making them computationally more efficient than all existing algorithms.
  arXiv  Detail & Related papers  (2021-06-15T19:15:17Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Quantum speedups of some general-purpose numerical optimisation algorithms [0.03078691410268859]
  We show that many techniques for global optimisation under a Lipschitz constraint can be accelerated near-quadratically. Second, we show that backtracking line search, an ingredient in quasi-Newton optimisation algorithms, can be accelerated up to quadratically. Third, we show that a component of the Nelder-Mead algorithm can be accelerated by up to a multiplicative factor of $O(sqrtn)$.
  arXiv  Detail & Related papers  (2020-04-14T14:04:47Z)
• 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)
• Parameterized Complexity Analysis of Randomized Search Heuristics [16.759797540118665]
  This chapter compiles a number of results that apply the theory of parameterized running-time analysis of randomized algorithms. We outline the main results and proof techniques for a collection of randomized searchs tasked to solve NP-hard optimization problems.
  arXiv  Detail & Related papers  (2020-01-15T03:43:56Z)

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.