論文の概要: 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$となる。
関連論文リスト
- A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation [6.853165736531941]
逆数外乱の存在下でのスパース平均推定のアルゴリズム的問題について検討する。
我々の主な貢献は、$mathrmpoly(k,log d,1/epsilon)$サンプルを用いて、エフェサブクアクラティック時間で実行される頑健なスパース平均推定アルゴリズムである。
論文 参考訳(メタデータ) (2024-03-07T18:23:51Z) - A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP
hierarchies [37.29025597886073]
多次元スケーリング(MDS)は、$n$オブジェクト間のペアワイドな相似性を低次元空間に埋め込む方法のファミリーである。
準多項式依存のMDSに対する最初の近似アルゴリズムは$Delta$である。
我々の分析は、低次元ユークリッド空間の幾何学を利用して、アスペクト比$Delta$への指数的依存を避けることができる。
論文 参考訳(メタデータ) (2023-11-29T17:42:05Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳(メタデータ) (2023-08-18T17:52:12Z) - 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) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳(メタデータ) (2022-09-06T23:37:31Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。