論文の概要: The $(1 + 1)$-EA in Dynamic Environments
- arxiv url: http://arxiv.org/abs/2606.13360v1
- Date: Thu, 11 Jun 2026 13:46:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-12 15:55:27.828009
- Title: The $(1 + 1)$-EA in Dynamic Environments
- Title（参考訳）: 動的環境における$(1 + 1)$-EA
- Authors: Georg Hasebe, Johannes Lengler, Raghu Raman Ravi,
- Abstract要約: 我々は,各世代が1,2,4,dots,2n-1$のランダムな置換を均一に使用する動的バイナリ値問題を考える。
効率よく到達するが、より小さな距離に達するには指数的な時間を要する。
- 参考スコア（独自算出の注目度）: 0.9298078773213346
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the $(1 + 1)$-EA in dynamic linear environments, where in every generation selection is performed with respect to a freshly sampled linear function with positive weights. We consider the Dynamic Binary Value problem, where each generation uses a uniformly random permutation of $1,2,4,\dots,2^{n-1}$, and a Uniform weight variant, where the weights are drawn independently from $\mathrm{Unif}(0,1)$. Both of them have recently been integrated into the IOHprofiler platform and empirically studied. For both models we prove a sharp threshold in the mutation parameter $χ$ for mutation rate $χ/n$. Below the threshold, the expected optimisation time is $\mathcal{O}(n\log n)$, whereas above it the runtime becomes $2^{Ω(n)}$. For the Dynamic Binary Value problem in the exponential regime, we also quantify at what distance from the optimum the optimisation process stagnates. We show that there is a second threshold: a distance that is efficiently reached, but reaching any smaller distance takes exponential time. This quantifies and proves previous empirical findings.
- Abstract（参考訳）: 動的線形環境における$(1 + 1)$-EAについて検討し、各世代選択において正の重みを持つ新しくサンプリングされた線形関数に対して実行される。
動的双対値問題は、各世代が1,2,4,\dots,2^{n-1}$のランダムな置換と、その重みが$\mathrm{Unif}(0,1)$から独立に引き出される一様ウェイト変量を用いている。
この2つは、最近IOHファウンサープラットフォームに統合され、実験的に研究されている。
どちらのモデルに対しても、突然変異率$ s/n$に対して、突然変異パラメータ$ s$ のシャープしきい値が証明される。
しきい値の下には、期待される最適化時間は$\mathcal{O}(n\log n)$であるが、上述のランタイムは$2^{Ω(n)}$となる。
指数的状態における動的二項値問題に対しては、最適化プロセスが停滞する最適値からの距離を定量化する。
効率よく到達するが、より小さな距離に達するには指数的な時間を要する。
これは過去の経験的発見を定量化し証明する。
関連論文リスト
- How Neural Reward Models Learn Features for Policy Optimization: A Single-Index Analysis [53.063298916923976]
r*(x) = *(langle *, xrangle)$ と $x sim N(0, I_d)$ でガウスの単一インデックスモデルでフィードバックを研究する。
まず、報酬重み付きサンプルから隠れた方向を*$で学習し、次に重み付きリッジ回帰により読み出し層に適合する2段階のニューラル報酬モデルを分析する。
論文 参考訳（メタデータ） (2026-05-23T22:00:38Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳（メタデータ） (2025-09-20T20:18:49Z) - 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) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function [0.0]
進化的アルゴリズムを動的に研究し、各世代ごとに異なる適合関数が選択される。
特に、最適化の最も難しい領域は最適化の周辺ではない。
論文 参考訳（メタデータ） (2020-10-26T08:55:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。