論文の概要: 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)$以上を失うことはないことを示した。 ここでは, 局所最適高さのランダムなゆらぎが, プラス戦略に対する破壊的な効果を示し, 超ポリノミアルランタイムに繋がることを示す。 一方,コマ戦略は局地最適から逃れる能力のため,局地最適の高さの影響を受けず,効率が保たれている。 以上の結果から,コマ戦略ではなくプラス戦略が,スムーズな景観の緩やかな非構造的ゆらぎによって認知されることが示唆された。

関連論文リスト

• Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback [49.84060509296641]
  オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。 この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。 この設定のための最初のポリシー最適化アルゴリズムを紹介します。
  論文  参考訳（メタデータ） (2025-02-06T12:03:24Z)
• Optimal Restart Strategies for Parameter-dependent Optimization Algorithms [0.0]
  本稿では,未知パラメータ$lambda$に依存するアルゴリズムの再起動戦略について検討する。 $lambda$のユニークな、未知の、最適な値が存在すると仮定される。 アルゴリズムが正常に動作するためには、この値を到達または超越する必要がある。
  論文  参考訳（メタデータ） (2025-01-17T13:14:53Z)
• 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)
• Provably Efficient Exploration in Policy Optimization [117.09887790160406]
  本稿では,最適化アルゴリズム(OPPO)の最適変種を提案する。 OPPO は $tildeO(sqrtd2 H3 T )$ regret を達成する。 我々の知る限りでは、OPPOは、探索する最初の証明可能な効率的なポリシー最適化アルゴリズムである。
  論文  参考訳（メタデータ） (2019-12-12T08:40:02Z)

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

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