Fugu-MT 論文翻訳(概要): Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments

論文の概要: Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments

arxiv url: http://arxiv.org/abs/2006.04663v3
Date: Sat, 31 Oct 2020 10:42:28 GMT
ステータス: 処理完了
システム内更新日: 2022-11-24 01:53:27.416635
Title: Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments
Title（参考訳）: 対称性論による進化アルゴリズムのランタイム解析
Authors: Benjamin Doerr
Abstract要約: Sutton and Witt (GECCO) が分析した選択自由定常遺伝的アルゴリズムは、特定のターゲット探索点を見つけるために、期待する数$Omega (2n / sqrt n)$を取ることを証明している。我々の結果は、以前の$Omega(exp(ndelta/2))$の下位境界よりも改善され、人口規模が$muに対して有効である。
参考スコア（独自算出の注目度）: 9.853329403413701
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We use an elementary argument building on group actions to prove that the selection-free steady state genetic algorithm analyzed by Sutton and Witt (GECCO 2019) takes an expected number of $\Omega(2^n / \sqrt n)$ iterations to find any particular target search point. This bound is valid for all population sizes $\mu$. Our result improves over the previous lower bound of $\Omega(\exp(n^{\delta/2}))$ valid for population sizes $\mu = O(n^{1/2 - \delta})$, $0 < \delta < 1/2$.
Abstract（参考訳）: Sutton and Witt (GECCO 2019) が分析した選択自由定常遺伝的アルゴリズムが、特定のターゲット探索点を見つけるために、期待される数$\Omega(2^n / \sqrt n)$イテレーションを取ることを証明するために、グループアクションに基本的な引数構造を用いる。この境界はすべての集団サイズに$\mu$で有効である。我々の結果は、以前の$\Omega(\exp(n^{\delta/2})$の下位境界よりも改善され、人口サイズが$\mu = O(n^{1/2\delta})$, $0 < \delta < 1/2$となる。

関連論文リスト

Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs [2.9123921488295768]
そこで本稿では,デジェネリティーに縛られた入力グラフに対して,局所的な差分プライバシーの下でサイクル数をカウントするアルゴリズムを提案する。我々のアルゴリズムは、退化性有界グラフに対して、$O(d_max0.5 n0.5) = O(n)$の予測$ell$-errorを達成する。
論文参考訳（メタデータ） (2024-09-25T07:23:58Z)
Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem [10.506038775815094]
我々は、小さなギャップの場合、$(mu+1)$EAが$O(mu2 m4 log(m))$の期待ランタイムで最大多様性を達成することを示す。 2P-EA_D$はより強力なパフォーマンスを示し、小さなギャップケースは$O(mu2 n2 log(m))$、パスは$O(mu3 m3)$である。
論文参考訳（メタデータ） (2024-04-17T22:20:02Z)
A Tight $O(4^k/p_c)$ Runtime Bound for a ($μ$+1) GA on Jump$_k$ for Realistic Crossover Probabilities [1.8434042562191815]
人口の多様性は、ほぼ完全な多様性の均衡に収束することを示す。私たちの仕事は、20年以上開かれてきた問題を部分的に解決します。
論文参考訳（メタデータ） (2024-04-10T14:50:43Z)
Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
我々は注意問題のスパシフィケーションを考慮する。超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
論文参考訳（メタデータ） (2023-04-10T05:52:38Z)
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)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
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)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文参考訳（メタデータ） (2020-06-02T16:38:36Z)
Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文参考訳（メタデータ） (2020-02-17T10:53:50Z)
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)

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