論文の概要: Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms
- arxiv url: http://arxiv.org/abs/1910.14389v2
- Date: Sun, 26 Nov 2023 11:08:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2023-11-30 18:22:43.320481
- Title: Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms
- Title（参考訳）: 分布アルゴリズム推定における遺伝的ドリフトのシャープ境界
- Authors: Benjamin Doerr, Weijie Zheng
- Abstract要約: 本稿では,中性ビットのサンプリング周波数の境界打点時間の最初の鋭い推定値を示す。
パラメータ $mu$, $lambda$, $rho$ が期待値 $Theta(mu/rho2)$ 中性ビットのサンプリング周波数 $[Theta(mu/mu), 1-Theta(rho/mu)]$ の間隔を残し、このビットに対して常に同じ値がサンプリングされることを示します。
- 参考スコア（独自算出の注目度）: 16.904475483445452
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Estimation of Distribution Algorithms (EDAs) are one branch of Evolutionary
Algorithms (EAs) in the broad sense that they evolve a probabilistic model
instead of a population. Many existing algorithms fall into this category.
Analogous to genetic drift in EAs, EDAs also encounter the phenomenon that
updates of the probabilistic model not justified by the fitness move the
sampling frequencies to the boundary values. This can result in a considerable
performance loss.
This paper proves the first sharp estimates of the boundary hitting time of
the sampling frequency of a neutral bit for several univariate EDAs. For the
UMDA that selects $\mu$ best individuals from $\lambda$ offspring each
generation, we prove that the expected first iteration when the frequency of
the neutral bit leaves the middle range $[\tfrac 14, \tfrac 34]$ and the
expected first time it is absorbed in 0 or 1 are both $\Theta(\mu)$. The
corresponding hitting times are $\Theta(K^2)$ for the cGA with hypothetical
population size $K$. This paper further proves that for PBIL with parameters
$\mu$, $\lambda$, and $\rho$, in an expected number of $\Theta(\mu/\rho^2)$
iterations the sampling frequency of a neutral bit leaves the interval
$[\Theta(\rho/\mu),1-\Theta(\rho/\mu)]$ and then always the same value is
sampled for this bit, that is, the frequency approaches the corresponding
boundary value with maximum speed.
For the lower bounds implicit in these statements, we also show exponential
tail bounds. If a bit is not neutral, but neutral or has a preference for ones,
then the lower bounds on the times to reach a low frequency value still hold.
An analogous statement holds for bits that are neutral or prefer the value
zero.
- Abstract（参考訳）: 分布アルゴリズムの推定 (EDAs) は、人口ではなく確率的モデルを進化させるという広義の進化的アルゴリズム(EA)の一分野である。
既存のアルゴリズムはこのカテゴリに分類される。
EAにおける遺伝的ドリフトと類似して、EDAは、適合性によって正当化されない確率モデルの更新がサンプリング周波数を境界値に移動する現象にも遭遇する。
これによりパフォーマンスが大幅に低下する可能性がある。
本稿では,複数の単変量EDAに対して中性ビットのサンプリング周波数の境界打点時間の最初の鋭い推定値を示す。
それぞれの世代で$\lambda$ offspringから$\mu$のベストな個人を選択するUMDAに対して、中立ビットの周波数がミドルレンジ$[\tfrac 14 \tfrac 34]$と0または1に吸収されたときに期待される最初のイテレーションが$\Theta(\mu)$であることを示す。
対応するヒットタイムは、仮説上の集団サイズが$K$のcGAに対して$\Theta(K^2)$である。
さらに,$\mu$,$\lambda$,$\rho$ のパラメータを持つ pbil に対して,期待値の $\theta(\mu/\rho^2)$ を繰り返すことで,中性ビットのサンプリング周波数が区間 $[\theta(\rho/\mu),1-\theta(\rho/\mu)] を残し,そのビットに対して常に同じ値がサンプリングされ,その周波数が最大速度で対応する境界値に近づくことを証明した。
これらのステートメントで暗黙的な下限に対しては、指数的テール境界も示される。
ビットが中性ではなく、中性である場合、あるいはそれを好む場合、低周波値に達するための時間上の下限は依然として保持される。
類似のステートメントは、中立あるいは0の値を好むビットに対して成り立つ。
関連論文リスト
- Debiasing and a local analysis for population clustering using
semidefinite programming [1.9761774213809036]
サブガウス分布の混合から引き出された小さいデータサンプルを$n$で分割する問題を考察する。
この研究は、起源の個体数に応じた集団化の応用によって動機付けられている。
論文 参考訳（メタデータ） (2024-01-16T03:14:24Z) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳（メタデータ） (2024-01-11T07:45:09Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳（メタデータ） (2020-09-30T04:44:45Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Learning Entangled Single-Sample Gaussians in the Subset-of-Signals
Model [28.839136703139225]
本研究は, 共通平均と異なる未知の分散を持つ絡み合った単一サンプルガウスの平均推定について検討する。
誤差が$O left(fracsqrtnln nmright)$m=Omega(sqrtnlnn)$の場合に高い確率でエラーを発生させることを示す。
さらに下限を証明し、エラーが$Omegaleft(left(fracnm4right)1/6right)$であることを示す。
論文 参考訳（メタデータ） (2020-07-10T18:25:38Z) - Inference on the change point in high dimensional time series models via
plug in least squares [2.7718973516070684]
本研究では,変化が高次元ランダムベクトルの平均となる点パラメータの最小2乗推定器について検討する。
この推定器が平均パラメータの推定におけるプラグに対する十分な適応性を持つ十分な条件を得る。
論文 参考訳（メタデータ） (2020-07-03T18:08:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。