論文の概要: A Tight $O(4^k/p_c)$ Runtime Bound for a ($μ$+1) GA on Jump$_k$ for Realistic Crossover Probabilities

• arxiv url: http://arxiv.org/abs/2404.07061v1
• Date: Wed, 10 Apr 2024 14:50:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-11 14:11:27.411376
• Title: A Tight $O(4^k/p_c)$ Runtime Bound for a ($μ$+1) GA on Jump$_k$ for Realistic Crossover Probabilities
• Title（参考訳）: A Tight $O(4^k/p_c)$ Runtime Bound for a$μ$+1) GA on Jump$_k$ for Realistic Crossover Probabilities
• Authors: Andre Opris, Johannes Lengler, Dirk Sudholt,
• Abstract要約: 人口の多様性は、ほぼ完全な多様性の均衡に収束することを示す。 私たちの仕事は、20年以上開かれてきた問題を部分的に解決します。
• 参考スコア（独自算出の注目度）: 1.8434042562191815
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The Jump$_k$ benchmark was the first problem for which crossover was proven to give a speedup over mutation-only evolutionary algorithms. Jansen and Wegener (2002) proved an upper bound of $O({\rm poly}(n) + 4^k/p_c)$ for the ($\mu$+1)~Genetic Algorithm ($(\mu+1)$ GA), but only for unrealistically small crossover probabilities $p_c$. To this date, it remains an open problem to prove similar upper bounds for realistic~$p_c$; the best known runtime bound for $p_c = \Omega(1)$ is $O((n/\chi)^{k-1})$, $\chi$ a positive constant. Using recently developed techniques, we analyse the evolution of the population diversity, measured as sum of pairwise Hamming distances, for a variant of the \muga on Jump$_k$. We show that population diversity converges to an equilibrium of near-perfect diversity. This yields an improved and tight time bound of $O(\mu n \log(k) + 4^k/p_c)$ for a range of~$k$ under the mild assumptions $p_c = O(1/k)$ and $\mu \in \Omega(kn)$. For all constant~$k$ the restriction is satisfied for some $p_c = \Omega(1)$. Our work partially solves a problem that has been open for more than 20 years.
• Abstract（参考訳）: Jump$_k$ベンチマークは、クロスオーバーが突然変異のみの進化アルゴリズムを高速化することを証明した最初の問題である。 Jansen and Wegener (2002) は$O({\rm poly)(n) + 4^k/p_c)$(\mu$+1)~Genetic Algorithm ($(\mu+1)$ GA)の上限を証明したが、非現実的に小さなクロスオーバー確率$p_c$に対してのみ証明した。 この日まで、p_c = \Omega(1)$ の最もよく知られたランタイム境界は $O((n/\chi)^{k-1})$, $\chi$ a positive constant である。 最近開発された手法を用いて、Jump$_k$ 上の \muga の変種に対して、ペアワイズハミング距離の和として測定された集団多様性の進化を分析する。 人口の多様性は、ほぼ完全な多様性の均衡に収束することを示す。 これにより、緩やかな仮定で、$p_c = O(1/k)$ と $\mu \in \Omega(kn)$ とすると、$O(\mu n \log(k) + 4^k/p_c)$ となる。 すべての定数~$k$に対して、ある$p_c = \Omega(1)$に対して制限が満たされる。 私たちの仕事は、20年以上開かれてきた問題を部分的に解決します。

関連論文リスト

• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm [7.421135890148154]
  集団サイズが$mu=O(n)$の遺伝的アルゴリズムは、ギャップサイズが$k ge 3$のジャンプ関数を最適化する。 この多様性は、(二次的ではなく)$mu$で指数関数的に高い確率で持続することを示す。 すべての$cln(n)lemu le n/log n$, with $c$ a suitable constant, the runtime of the $(mu+1)$ GA on $mathrmJump_k$, with $k
  論文  参考訳（メタデータ） (2023-02-24T10:50:24Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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