論文の概要: Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift

• arxiv url: http://arxiv.org/abs/2005.00853v4
• Date: Tue, 20 Oct 2020 09:04:46 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-07 12:43:31.512668
• Title: Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative Multiplicative Drift
• Title（参考訳）: 負乗法ドリフトによる非楕円型進化アルゴリズムの下限
• Authors: Benjamin Doerr
• Abstract要約: 乗法的ドリフトシナリオに対する単純な負のドリフト定理は既存の解析を単純化できることを示す。 我々は、非エリート変異に基づく進化アルゴリズムのランタイムにおける下位境界を証明するための最も一般的なツールの1つである集団法において、Lehre's emph negative drift in populations法(PPSN 2010)についてより詳細に論じる。
• 参考スコア（独自算出の注目度）: 9.853329403413701
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A decent number of lower bounds for non-elitist population-based evolutionary algorithms has been shown by now. Most of them are technically demanding due to the (hard to avoid) use of negative drift theorems -- general results which translate an expected progress away from the target into a high hitting time. We propose a simple negative drift theorem for multiplicative drift scenarios and show that it can simplify existing analyses. We discuss in more detail Lehre's (PPSN 2010) \emph{negative drift in populations} method, one of the most general tools to prove lower bounds on the runtime of non-elitist mutation-based evolutionary algorithms for discrete search spaces. Together with other arguments, we obtain an alternative and simpler proof, which also strengthens and simplifies this method. In particular, now only three of the five technical conditions of the previous result have to be verified. The lower bounds we obtain are explicit instead of only asymptotic. This allows to compute concrete lower bounds for concrete algorithms, but also enables us to show that super-polynomial runtimes appear already when the reproduction rate is only a $(1 - \omega(n^{-1/2}))$ factor below the threshold. For the special case of algorithms using standard bit mutation with a random mutation rate (called uniform mixing in the language of hyper-heuristics), we prove the result stated by Dang and Lehre (PPSN 2016) and extend it to mutation rates other than $\Theta(1/n)$, which includes the heavy-tailed mutation operator proposed by Doerr, Le, Makhmara, and Nguyen (GECCO 2017). We finally apply our method and a novel domination argument to show an exponential lower bound for the runtime of the mutation-only simple genetic algorithm on \onemax for arbitrary population size.
• Abstract（参考訳）: 非エリート型人口ベースの進化的アルゴリズムのかなり低い範囲が、現在までに示されている。 それらのほとんどが技術的に要求されているのは、負のドリフト定理(英語版)(負のドリフト定理)の使用(回避が難しい)のためである。 本研究では,乗法ドリフトシナリオに対する単純な負ドリフト定理を提案し,既存の解析を単純化できることを示す。 離散探索空間に対する非エリート変異に基づく進化的アルゴリズムのランタイムにおける下位境界を証明するための最も一般的なツールの1つである、Lehre's (PPSN 2010) \emph{ negative drift in populations} についてより詳しく論じる。 他の議論とともに、この方法を強化し、単純化する代替的で単純な証明を得る。 特に、これまでの5つの技術的条件のうち3つのみが検証されなければならない。 得られる下限は漸近的ではなく明示的である。 これにより、具体的なアルゴリズムに対する具体的な下限を計算できるが、再生率が1-\omega(n^{-1/2})$値以下である場合に既に超多項式ランタイムが現れることを示すこともできる。 ランダムな突然変異率(超ヒューリスティックス言語では均一混合と呼ばれる)を持つ標準ビット突然変異を用いるアルゴリズムの特別な場合については、dang and lehre (ppsn 2016) による結果を証明し、doerr, le, makhmara, nguyen (gecco 2017) によって提案された重尾の突然変異演算子を含む$\theta(1/n)$以外の突然変異率に拡張する。 最後に,この手法と新しい支配論を応用し,任意の集団サイズに対して1max上の突然変異のみの単純遺伝的アルゴリズムの実行時の指数関数的下限を示す。

関連論文リスト

• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms [4.307128674848627]
  AdaPG$q,r$は、より大きな段階的なポリシーと改善された下位境界を提供することで、既存の結果を統一し、拡張するフレームワークである。 パラメータの$q$と$r$の異なる選択について論じ、数値シミュレーションにより結果の有効性を実証する。
  論文  参考訳（メタデータ） (2023-11-30T10:29:43Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
  論文  参考訳（メタデータ） (2023-10-27T09:16:58Z)
• Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes [4.553891255178496]
  微分プライベートアルゴリズムのサンプル複雑性に基づいて,スムーズな下界を生成するための新しいフレームワークとツールを提案する。 我々の主な技術は、指紋コードにパディング・アンド・パーミュート変換を適用することである。 我々はDwork et al. (FOCS 2015) と Bun et al. (SODA 2017) より強い新しい指紋認証補題を開発する。
  論文  参考訳（メタデータ） (2023-07-14T19:58:02Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  ランダムに選択されたデータバッチの分類出力行列の構造について検討し,予測可能性と多様性について検討した。 本稿では,目標出力行列上で核ノルムを行い,目標予測能力を向上するBatch Nuclear-norm Maximization and Minimizationを提案する。 実験により,本手法は3つの典型的なドメイン適応シナリオにおいて適応精度とロバスト性を高めることができることが示された。
  論文  参考訳（メタデータ） (2021-07-13T15:08:32Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。 これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
  論文  参考訳（メタデータ） (2020-05-07T19:59:51Z)
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm [15.56430085052365]
  遺伝的なドリフトのない体制では、実行期間は人口規模にほぼ比例する。 本稿では,遺伝的アルゴリズムのパラメータレスバージョンを提案する。
  論文  参考訳（メタデータ） (2020-04-15T15:12:01Z)
• Exponential Upper Bounds for the Runtime of Randomized Search Heuristics [9.853329403413701]
  アルゴリズムの任意のランダム化ローカルサーチ,アルゴリズム,シミュレートされたアニーリング,および (1+1) 進化的アルゴリズムが,任意の擬ブール弱単調関数を最適化可能であることを示す。 また、OneMaxベンチマークにおいて、単純な遺伝的アルゴリズムの突然変異に基づくバージョンの実行時の指数的な上限を証明した。
  論文  参考訳（メタデータ） (2020-04-13T00:24:33Z)
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes [9.853329403413701]
  単変量分布アルゴリズム(UMDA)における実行時間保証の強化を実証する。 より少ない選択率によるランタイムゲインを示す。 同様の仮定の下では、我々の上界と定数因子に一致する境界が高い確率で成り立つことを証明している。
  論文  参考訳（メタデータ） (2020-04-10T10:20:05Z)

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

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