論文の概要: Plus Strategies are Exponentially Slower for Planted Optima of Random Height

• arxiv url: http://arxiv.org/abs/2404.09687v1
• Date: Mon, 15 Apr 2024 11:37:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-16 12:40:28.457109
• Title: Plus Strategies are Exponentially Slower for Planted Optima of Random Height
• Title（参考訳）: プラス戦略はランダム高さの植え付けオプティマスの指数的に遅い
• Authors: Johannes Lengler, Leon Schiller, Oliver Sieberling,
• Abstract要約: 局所オプティマの高さの小さなランダムな変動でさえプラス戦略に破壊的な効果を示し、超ポリノミアルランタイムに繋がることを示した。 以上の結果から,コンマ戦略ではなくプラス戦略が,スムーズな景観の緩やかな非構造的ゆらぎによって認知されることが示唆された。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We compare the $(1,\lambda)$-EA and the $(1 + \lambda)$-EA on the recently introduced benchmark DisOM, which is the OneMax function with randomly planted local optima. Previous work showed that if all local optima have the same relative height, then the plus strategy never loses more than a factor $O(n\log n)$ compared to the comma strategy. Here we show that even small random fluctuations in the heights of the local optima have a devastating effect for the plus strategy and lead to super-polynomial runtimes. On the other hand, due to their ability to escape local optima, comma strategies are unaffected by the height of the local optima and remain efficient. Our results hold for a broad class of possible distortions and show that the plus strategy, but not the comma strategy, is generally deceived by sparse unstructured fluctuations of a smooth landscape.
• Abstract（参考訳）: 最近導入されたベンチマークDisOMで、$(1,\lambda)$-EAと$(1 + \lambda)$-EAを比較した。 以前の研究は、すべての局所最適化が同じ相対的な高さを持つなら、プラス戦略はコマ戦略と比較して$O(n\log n)$以上を失うことはないことを示した。 ここでは, 局所最適高さのランダムなゆらぎが, プラス戦略に対する破壊的な効果を示し, 超ポリノミアルランタイムに繋がることを示す。 一方,コマ戦略は局地最適から逃れる能力のため,局地最適の高さの影響を受けず,効率が保たれている。 以上の結果から,コマ戦略ではなくプラス戦略が,スムーズな景観の緩やかな非構造的ゆらぎによって認知されることが示唆された。

関連論文リスト

• Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
  本稿では,次数$tildemathcalO(mathrmpoly(H)sqrtSAT)$の残差を求めるアルゴリズムを提案する。 提案したアルゴリズムと分析は、占有対策によって与えられる典型的なツールを完全に回避する。
  論文  参考訳（メタデータ） (2024-07-08T08:06:45Z)
• AlphaZeroES: Direct score maximization outperforms planning loss minimization [61.17702187957206]
  実行時の計画では、シングルエージェントとマルチエージェントの両方の設定でエージェントのパフォーマンスが劇的に向上することが示されている。 実行時に計画するアプローチのファミリは、AlphaZeroとその変種で、Monte Carlo Tree Searchと、状態値とアクション確率を予測することによって検索をガイドするニューラルネットワークを使用する。 複数の環境にまたがって、エピソードスコアを直接最大化し、計画損失を最小限に抑えることを示す。
  論文  参考訳（メタデータ） (2024-06-12T23:00:59Z)
• Self-Adjusting Evolutionary Algorithms Are Slow on Multimodal Landscapes [0.0]
  正の結果が他の局所最適値に拡張されないことを示す。 歪んだOneMaxベンチマークでは、自己調整の$(1, lambda)$-EAは、アルゴリズムがローカルオプティマからエスケープされるのを防ぐため、エリート的アルゴリズムと同じように遅くなる。
  論文  参考訳（メタデータ） (2024-04-18T10:01:08Z)
• Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima [0.0]
  このベンチマークでは、コンマの選択($(1,lambda)$ EA)が、選択($(1+lambda)$ EA)よりも高速であることを示す。 凍結音を解析するための新しい手法を開発し、独立性のある尾境界を持つ強力で汎用的な固定目標値を与える。
  論文  参考訳（メタデータ） (2023-04-19T15:00:14Z)
• Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus [48.34563955829649]
  本稿では,共同戦略の信頼区間を構築する戦略的な集中原理を提案する。 2人のプレイヤーによるゼロサムマルコフゲームの場合、戦略的なボーナスの凸性を利用して効率的なアルゴリズムを提案する。 すべてのアルゴリズムは、指定済みの戦略クラスである$Pi$を入力として取り、最良の戦略に近い戦略を$Pi$で出力することができる。
  論文  参考訳（メタデータ） (2022-06-01T00:18:15Z)
• Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
  最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。 次に,政策最適化におけるコミット率の概念を紹介する。 第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
  論文  参考訳（メタデータ） (2021-10-29T06:35:44Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax [1.0965065178451106]
  我々は、最適な突然変異率の分析を、OneMax問題の2つの変種に拡張する。 すべての集団サイズを2i mid 0 le i le 18$で計算します。 我々の結果は、一般的な進化的アプローチを測ることのできる低い境界を提供するばかりではない。
  論文  参考訳（メタデータ） (2020-06-20T01:23:14Z)
• Does Comma Selection Help To Cope With Local Optima [9.853329403413701]
  我々は、$(mu,lambda)$EAが$(mu+lambda)$EAに対してランタイム上の優位性をもたらすことはないことを示した。 これは、低次項から遠ざかるマルチモーダル問題に対する非エリートアルゴリズムの最初の実行時結果である。
  論文  参考訳（メタデータ） (2020-04-02T21:39:33Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。 我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
  論文  参考訳（メタデータ） (2020-02-19T15:41:18Z)
• Provably Efficient Exploration in Policy Optimization [117.09887790160406]
  本稿では,最適化アルゴリズム(OPPO)の最適変種を提案する。 OPPO は $tildeO(sqrtd2 H3 T )$ regret を達成する。 我々の知る限りでは、OPPOは、探索する最初の証明可能な効率的なポリシー最適化アルゴリズムである。
  論文  参考訳（メタデータ） (2019-12-12T08:40:02Z)

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

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