論文の概要: Runtime Analysis of the $(μ+ 1)$-ES in a Homogenous Progress Model
- arxiv url: http://arxiv.org/abs/2606.13323v1
- Date: Thu, 11 Jun 2026 13:15:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-12 15:55:27.813671
- Title: Runtime Analysis of the $(μ+ 1)$-ES in a Homogenous Progress Model
- Title（参考訳）: 均質進行モデルにおける$(μ+ 1)$-ESの実行時解析
- Authors: Johannes Lengler, Raghu Raman Ravi,
- Abstract要約: 一般的な問題における進化戦略(ES)の適合性に関する新しい単純なモデルを提案する。
任意の個体の突然変異は、親に対する適合度が不変分布$Z$で与えられる子孫を生成すると仮定する。
これは、進化アルゴリズムが大域的最適から遠く離れているとき、最適化ランドスケープの原型モデルとして機能する。
- 参考スコア（独自算出の注目度）: 1.0450108735332535
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a new simple model to study the fitness progress of Evolution Strategies (ES) in generic problems. In this model, we bypass the underlying fitness landscape and assume that the mutation of any individual produces an offspring whose fitness relative to the parent is given by an invariant distribution $Z$, such as a mean-shifted Gaussian. This serves as a prototypical model for the optimisation landscape when an evolution algorithm operates far from the global optimum. This simple model can be used to approximate the optimisation process for problems where it is intractable to model the exact fitness function, including tasks such as hyperparameter tuning in machine learning models. We rigorously analyse the expected growth rate $\mathcal{R}_μ$ of the continuous steady-state $(μ+1)$-ES in this model. Unlike comma-selection strategies, the steady-state $(μ+1)$-ES maintains overlapping generations, introducing complex mathematical dependencies among surviving parents that make it harder to analyse. We give a general technique to analyse the the $(μ+ 1)$-ES by constructing modified processes whose growth rates provably sandwich that of the original process. These modified processes are then easier to analyse but still close enough to the true process to give a tight bound on the expected growth rate. When $Z = \mathcal{N}(-δ, 1)$ and $μ\le e^δ$, we show that $\mathcal{R}_μ = \frac{\log^{1 + o(1)} μ}μ \mathcal{R}_1$.
- Abstract（参考訳）: 一般的な問題における進化戦略(ES)の適合性に関する新しい単純なモデルを提案する。
このモデルでは、基礎となるフィットネス・ランドスケープをバイパスし、親に対する適合度が平均シフトガウス等不変分布$Z$で与えられる子孫を生成すると仮定する。
これは、進化アルゴリズムが大域的最適から遠く離れているとき、最適化ランドスケープの原型モデルとして機能する。
この単純なモデルは、機械学習モデルにおけるハイパーパラメータチューニングなどのタスクを含む、正確な適合関数をモデル化し難い問題に対する最適化プロセスの近似に使用できる。
このモデルにおける連続定常状態$(μ+1)$-ESの予測成長率$\mathcal{R}_μ$を厳密に分析する。
コンマ選択戦略とは異なり、安定状態$(μ+1)$-ESは重複世代を維持し、生き残った親の間で複雑な数学的依存関係を導入し、分析しにくくする。
成長速度が元のプロセスのものを確実にサンドイッチする修正プロセスを構築することにより、$(μ+ 1)$-ESを解析するための一般的な手法を提供する。
これらの修正されたプロセスは、分析し易いが、期待される成長速度に固執する真のプロセスにはまだ十分近い。
Z = \mathcal{N}(-δ, 1)$ と $μ\le e^δ$ のとき、$\mathcal{R}_μ = \frac{\log^{1 + o(1)} μ}μ \mathcal{R}_1$ を示す。
関連論文リスト
- Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。
パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
論文 参考訳（メタデータ） (2025-10-06T10:53:37Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus [9.853329403413701]
本研究では, 離散フーリエ解析に基づく新しい手法を提案し, 進化的アルゴリズムがプラトーに費やす時間を解析する。
また、この手法を用いて、$(1+1)$進化アルゴリズムのランタイムを、有効サイズ2ell-1$の$n/ell$高原からなる新しいベンチマークで解析する。
論文 参考訳（メタデータ） (2023-02-16T01:46:06Z) - KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。
我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
論文 参考訳（メタデータ） (2022-05-27T19:39:24Z) - SGD Through the Lens of Kolmogorov Complexity [0.15229257192293197]
勾配降下 (SGD) はデータセット全体の分類精度が$ (1-epsilon)$の解を求める。
特定のアーキテクチャやアクティベーション関数を持つためにモデルを必要としないのです。
論文 参考訳（メタデータ） (2021-11-10T01:32:38Z) - Model Selection with Near Optimal Rates for Reinforcement Learning with
General Model Classes [27.361399036211694]
有限地平線エピソディック強化学習(RL)問題に対するモデル選択の問題に対処する。
モデル選択フレームワークでは、$mathcalP*$の代わりに、遷移カーネルのネストされたファミリーが$M$を与えられる。
textttARL-GENが$TildemathcalO(d_mathcalE* H2+sqrtd_mathcalE* mathbbM* H2T)$の後悔を得ることを示す。
論文 参考訳（メタデータ） (2021-07-13T05:00:38Z) - Learning to extrapolate using continued fractions: Predicting the
critical temperature of superconductor materials [5.905364646955811]
人工知能(AI)と機械学習(ML)の分野では、未知のターゲット関数 $y=f(mathbfx)$ の近似が共通の目的である。
トレーニングセットとして$S$を参照し、新しいインスタンス$mathbfx$に対して、このターゲット関数を効果的に近似できる低複雑さの数学的モデルを特定することを目的としている。
論文 参考訳（メタデータ） (2020-11-27T04:57:40Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。