論文の概要: Nonequilibrium Monte Carlo for unfreezing variables in hard
combinatorial optimization
- arxiv url: http://arxiv.org/abs/2111.13628v1
- Date: Fri, 26 Nov 2021 17:45:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-29 18:14:43.065678
- Title: Nonequilibrium Monte Carlo for unfreezing variables in hard
combinatorial optimization
- Title（参考訳）: ハードコンビネート最適化における非凍結変数に対する非平衡モンテカルロ
- Authors: Masoud Mohseni, Daniel Eppens, Johan Strumpfer, Raffaele Marino, Vasil
Denchev, Alan K. Ho, Sergei V. Isakov, Sergio Boixo, Federico
Ricci-Tersenghi, Hartmut Neven
- Abstract要約: 適応的勾配自由戦略を開発することにより,非局所非平衡モンテカルロ(NMC)アルゴリズムの量子インスパイアされたファミリーを導入する。
我々は、特殊解法と汎用解法の両方に対して、大幅な高速化と堅牢性を観察する。
- 参考スコア（独自算出の注目度）: 1.1783108699768
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Optimizing highly complex cost/energy functions over discrete variables is at
the heart of many open problems across different scientific disciplines and
industries. A major obstacle is the emergence of many-body effects among
certain subsets of variables in hard instances leading to critical slowing down
or collective freezing for known stochastic local search strategies. An
exponential computational effort is generally required to unfreeze such
variables and explore other unseen regions of the configuration space. Here, we
introduce a quantum-inspired family of nonlocal Nonequilibrium Monte Carlo
(NMC) algorithms by developing an adaptive gradient-free strategy that can
efficiently learn key instance-wise geometrical features of the cost function.
That information is employed on-the-fly to construct spatially inhomogeneous
thermal fluctuations for collectively unfreezing variables at various length
scales, circumventing costly exploration versus exploitation trade-offs. We
apply our algorithm to two of the most challenging combinatorial optimization
problems: random k-satisfiability (k-SAT) near the computational phase
transitions and Quadratic Assignment Problems (QAP). We observe significant
speedup and robustness over both specialized deterministic solvers and generic
stochastic solvers. In particular, for 90% of random 4-SAT instances we find
solutions that are inaccessible for the best specialized deterministic
algorithm known as Survey Propagation (SP) with an order of magnitude
improvement in the quality of solutions for the hardest 10% instances. We also
demonstrate two orders of magnitude improvement in time-to-solution over the
state-of-the-art generic stochastic solver known as Adaptive Parallel Tempering
(APT).
- Abstract（参考訳）: 離散変数に対して非常に複雑なコスト/エネルギー関数を最適化することは、様々な科学分野や産業にまたがる多くの開問題の中心である。
主な障害は、ハードインスタンスにおける変数の特定のサブセット間で多体効果が出現し、既知の確率的局所探索戦略において致命的な減速または集団凍結をもたらすことである。
指数計算の努力は一般にそのような変数を解凍し、構成空間の他の見えない領域を探索するために必要である。
ここでは,非局所非平衡モンテカルロ(NMC)アルゴリズムの量子インスパイアされたファミリーを導入し,コスト関数の重要なインスタンス単位の幾何学的特徴を効率的に学習できる適応的勾配のない戦略を開発した。
この情報は、様々な長さの変数をまとめて凍結する空間的不均一な熱ゆらぎを構築するために、オンザフライで使用される。
本アルゴリズムは,計算相転移近傍のk-SAT(ランダムk-satisfiability)と擬似アサインメント問題(QAP)の2つの最も困難な組合せ最適化問題に適用する。
我々は、特殊決定論的解法と一般確率論的解法の両方に対する顕著なスピードアップとロバスト性を観察した。
特に、ランダムな4-SATインスタンスの90%については、最も厳しい10%のインスタンスに対するソリューションの品質を大幅に改善したサーベイ・プロパゲーション(SP)と呼ばれる、最高の特殊決定論的アルゴリズムにはアクセスできない解を見つけます。
また,Adaptive Parallel Tempering (APT) と呼ばれる最先端の一般確率解法に対して,時間と解の2つの大域的改善を示す。
関連論文リスト
- Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。
数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
論文 参考訳（メタデータ） (2024-09-02T12:55:27Z) - Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。
このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
論文 参考訳（メタデータ） (2024-07-29T13:54:28Z) - Federated Conditional Stochastic Optimization [110.513884892319]
条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。
本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-04T01:47:37Z) - Numerical Methods for Convex Multistage Stochastic Optimization [86.45244607927732]
最適化プログラミング(SP)、最適制御(SOC)、決定プロセス(MDP)に焦点を当てる。
凸多段マルコフ問題の解決の最近の進歩は、動的プログラミング方程式のコスト対ゴー関数の切断面近似に基づいている。
切削平面型法は多段階問題を多段階的に扱えるが、状態(決定)変数は比較的少ない。
論文 参考訳（メタデータ） (2023-03-28T01:30:40Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - Sampling diverse near-optimal solutions via algorithmic quantum
annealing [0.3506539188356145]
主要な開問題の1つは、典型的なモンテカルロ解法に対するエルゴディディティの欠如、あるいはモード崩壊である。
本稿ではNP-hard最適化問題に対する独立近似解の数を定量化する新しい多様性尺度を提案する。
論文 参考訳（メタデータ） (2021-10-20T13:33:37Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳（メタデータ） (2021-05-05T03:36:00Z) - Adaptive variational quantum eigensolvers for highly excited states [4.038971004196936]
量子多体系の高励起状態は、量子力学と熱化の研究の中心的な対象である。
本稿では,多体ハミルトンの任意の固有状態に対する変分アンサッツを自己生成する適応的変分アルゴリズム VQE-X を提案する。
論文 参考訳（メタデータ） (2021-04-26T15:03:51Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - Bayesian optimization of variable-size design space problems [0.0]
このタイプの最適化問題を解決するために,ベイズ最適化に基づく2つのアプローチが提案されている。
最初のアプローチは、最も有望な設計サブスペースに計算予算を集中させるための予算配分戦略である。
第二のアプローチは、部分的に異なる変数の集合によって特徴づけられるサンプル間の共分散を計算することができるカーネル関数の定義に基づいている。
論文 参考訳（メタデータ） (2020-03-06T16:30:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。