論文の概要: Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2410.23270v1
• Date: Wed, 30 Oct 2024 17:52:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-31 14:26:02.346366
• Title: Generalized Short Path Algorithms: Towards Super-Quadratic Speedup over Markov Chain Search for Combinatorial Optimization
• Title（参考訳）: 一般化されたショートパスアルゴリズム:組合せ最適化のためのマルコフ連鎖探索による超量子スピードアップを目指して
• Authors: Shouvanik Chakrabarti, Dylan Herman, Guneykan Ozgul, Shuchen Zhu, Brandon Augustino, Tianyi Hao, Zichang He, Ruslan Shaydulin, Marco Pistoia,
• Abstract要約: 本稿ではHastingsが最初に提案したショートパスフレームワークに基づいてアルゴリズムの一般化を分析する。 一般的に満たされているいくつかの技術的条件の下では、適切な一般化は超4次スピードアップを達成することができる。 本論文は,短経路アルゴリズムのパラメータ選択を導く数値解析で締めくくった。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 本稿では,Hastings [Quantum 2, 78 (2018)] が提案したショートパスフレームワークに基づくアルゴリズムの一般化について解析する。 また, マルコフ連鎖の定常分布から標本を抽出し, 最適解を求める古典的最適化アルゴリズムを用いて, 適度な一般化を達成できることを実証した。 このフレームワークを用いて、Max-Bisection、Max Independent Set、Ising Model、Sherrington Kirkpatrick Modelの変種を含む問題のアルゴリズムを得る。 十分に高次なランダムな正則グラフの場合、我々のアルゴリズムは正則グラフに対する最も厳密に証明された古典的ランタイムよりも超四分法的に高速である。 また、NP = RP がなければ、我々のアルゴリズムが任意の多項式時間 Gibbs サンプリング器よりも超二乗的に高速な設定を同定することで、ショートパスアルゴリズムの量子的性質に光を当てた。 本論文は, 短経路アルゴリズムのパラメータの選択を導く数値解析を用いて結論付け, 理論的解析を超越した条件下での超2次高速化の可能性を高めるものである。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Run Time Analysis for Random Local Search on Generalized Majority Functions [1.0965065178451106]
  我々は、その性質の1つ、中立性がランダムな局所探索の実行時間にどのように影響するかを研究する。 我々は、多くの最適化アルゴリズムに適用可能な定理を提案し、MAJORITYの実行時間と対称バージョンHASMAJORITYをリンクする。
  論文  参考訳（メタデータ） (2022-04-27T08:40:33Z)
• Fast optimal structures generator for parameterized quantum circuits [4.655660925754175]
  現在の構造最適化アルゴリズムは、変分量子アルゴリズム(VQA)の新しいタスクごとにスクラッチから量子回路の構造を最適化する 本稿では,量子ゲート数を自動的に決定し,新しいタスクに最適な構造を直接生成する,VQAの高速構造最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-01-10T12:19:37Z)
• Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path [29.289190242826688]
  本稿では,最短経路(SSP)モデルにおいて,後悔するアルゴリズムを開発するための汎用テンプレートを提案する。 まず、厳密な正のコストでモデルフリーとミニマックス最適の2つの新しいアルゴリズムを開発する。 どちらのアルゴリズムも高度にスパースな更新を認めており、既存のアルゴリズムよりも計算効率が良い。
  論文  参考訳（メタデータ） (2021-06-15T19:15:17Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Quantum speedups of some general-purpose numerical optimisation algorithms [0.03078691410268859]
  リプシッツ制約の下での大域的最適化のための多くの手法は、ほぼ四分法的に加速できることを示す。 第2に、準ニュートン最適化アルゴリズムの成分であるバックトラックライン探索を2次に高速化できることを示す。 第三に、Nelder-Meadアルゴリズムの成分は最大$O(sqrtn)$の乗算係数で加速できることを示す。
  論文  参考訳（メタデータ） (2020-04-14T14:04:47Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Parameterized Complexity Analysis of Randomized Search Heuristics [16.759797540118665]
  この章では、ランダム化アルゴリズムのパラメータ化実行時間解析の理論を適用した多数の結果をまとめた。 NP-hard最適化問題の解法を課題とするランダム化検索の集合に対する主な結果と証明手法について概説する。
  論文  参考訳（メタデータ） (2020-01-15T03:43:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。