論文の概要: How Well Does the Metropolis Algorithm Cope With Local Optima?

• arxiv url: http://arxiv.org/abs/2304.10848v2
• Date: Mon, 15 May 2023 08:55:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-16 21:04:27.260714
• Title: How Well Does the Metropolis Algorithm Cope With Local Optima?
• Title（参考訳）: metropolisアルゴリズムは、ローカルオプティマに対してどの程度うまく対処できるのか?
• Authors: Benjamin Doerr, Taha El Ghazi El Houssaini, Amirhossein Rajabi, and Carsten Witt
• Abstract要約: 我々はCLIFFベンチマークでメトロポリスアルゴリズム(MA)のランタイム解析を行う。 MAが主要な動作原理から利益を得るための理想的なベンチマークであるように見えるが、数学的ランタイム分析は、この望みが実現していないことを示している。 この結果は、MAが実際に非常に成功した理由に関する我々の理解が、まだ完了していないことを示唆している。
• 参考スコア（独自算出の注目度）: 6.793248433673384
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Metropolis algorithm (MA) is a classic stochastic local search heuristic. It avoids getting stuck in local optima by occasionally accepting inferior solutions. To better and in a rigorous manner understand this ability, we conduct a mathematical runtime analysis of the MA on the CLIFF benchmark. Apart from one local optimum, cliff functions are monotonically increasing towards the global optimum. Consequently, to optimize a cliff function, the MA only once needs to accept an inferior solution. Despite seemingly being an ideal benchmark for the MA to profit from its main working principle, our mathematical runtime analysis shows that this hope does not come true. Even with the optimal temperature (the only parameter of the MA), the MA optimizes most cliff functions less efficiently than simple elitist evolutionary algorithms (EAs), which can only leave the local optimum by generating a superior solution possibly far away. This result suggests that our understanding of why the MA is often very successful in practice is not yet complete. Our work also suggests to equip the MA with global mutation operators, an idea supported by our preliminary experiments.
• Abstract（参考訳）: メトロポリスアルゴリズム (MA) は古典的な確率的局所探索ヒューリスティックである。 時折劣る解を受け入れることにより、局所最適状態に陥ることを避ける。 厳密な方法でこの能力を理解するために,我々はCLIFFベンチマーク上でMAの数学的ランタイム解析を行う。 1つの局所的な最適性とは別に、崖関数はグローバルな最適性に向かって単調に増大している。 したがって、崖関数を最適化するためには、MAは一度だけ劣る解を受け入れる必要がある。 MAが主要な動作原理から利益を得るための理想的なベンチマークであるように見えるが、数学的ランタイム分析は、この望みが実現していないことを示している。 最適温度(MAの唯一のパラメータ)であっても、MAは単純なエリート主義進化アルゴリズム(EA)よりも効率の悪い崖関数を最適化する。 この結果は、MAが実際に非常に成功した理由に関する我々の理解が、まだ完了していないことを示唆している。 私たちの研究はまた、maにグローバル変異演算子を装備することを提案しています。

関連論文リスト

• Hyper-Heuristics Can Profit From Global Variation Operators [12.774575491521926]
  モーブアクセプタンス・ハイパーヒューリスティック(MAHH)は,マルチモーダルCLIFFベンチマークの局所的最適化を極めて効率よく残していることを示す。 また、MAHHの局所的な1ビット突然変異演算子を、EAで一般的に使用されるグローバルビットワイズ演算子に置き換えると、JUMP関数上の$min1, O(fraceln(n)m)m, O(nm)$のランタイムが得られることを示す。
  論文  参考訳（メタデータ） (2024-07-19T12:10:05Z)
• Self-Adjusting Evolutionary Algorithms Are Slow on Multimodal Landscapes [0.0]
  正の結果が他の局所最適値に拡張されないことを示す。 歪んだOneMaxベンチマークでは、自己調整の$(1, lambda)$-EAは、アルゴリズムがローカルオプティマからエスケープされるのを防ぐため、エリート的アルゴリズムと同じように遅くなる。
  論文  参考訳（メタデータ） (2024-04-18T10:01:08Z)
• Efficient Minimax Optimal Global Optimization of Lipschitz Continuous Multivariate Functions [0.0]
  我々は,このアルゴリズムがリプシッツ連続函数の地平線に対して平均的後悔O(LstnT-frac1n)$を達成することを示す。
  論文  参考訳（メタデータ） (2022-06-06T06:28:38Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。 本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。 これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
  論文  参考訳（メタデータ） (2021-04-19T17:22:11Z)
• Why Do Local Methods Solve Nonconvex Problems? [54.284687261929115]
  非使用最適化は、現代の機械学習においてユビキタスである。 機械学習問題の場合、厳格に定式化します。 我々はこの現象の統一的な説明を仮定する。
  論文  参考訳（メタデータ） (2021-03-24T19:34:11Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• The Archerfish Hunting Optimizer: a novel metaheuristic algorithm for global optimization [0.8315801422499861]
  グローバル最適化は、目的関数を最小化することにより、現実の問題を数値的にあるいは分析的に解決する。 我々はArcherfish Hunting (AHO)に基づくグローバルメタヒスティックアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-03T16:22:31Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Incorporating Expert Prior in Bayesian Optimisation via Space Warping [54.412024556499254]
  大きな探索空間では、アルゴリズムは関数の最適値に達する前に、いくつかの低関数値領域を通過する。 このコールドスタートフェーズの1つのアプローチは、最適化を加速できる事前知識を使用することである。 本稿では,関数の事前分布を通じて,関数の最適性に関する事前知識を示す。 先行分布は、探索空間を最適関数の高確率領域の周りに拡張し、最適関数の低確率領域の周りに縮小するようにワープする。
  論文  参考訳（メタデータ） (2020-03-27T06:18:49Z)

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

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