論文の概要: Lower Bounds from Fitness Levels Made Easy
- arxiv url: http://arxiv.org/abs/2104.03372v1
- Date: Wed, 7 Apr 2021 19:50:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-09 12:57:21.324234
- Title: Lower Bounds from Fitness Levels Made Easy
- Title（参考訳）: フィットネスレベルから下限は簡単になった
- Authors: Benjamin Doerr and Timo K\"otzing
- Abstract要約: Wegenerによるいわゆるフィットネスレベルの方法の2つの新しい変種を示す。
レベル離脱確率の他に、彼らはレベルが訪問される確率にのみ依存している。
より困難を伴わずに計算や推定が可能であることを示し,本手法を適用して以下の既知結果を再現する。
- 参考スコア（独自算出の注目度）: 5.177947445379688
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: One of the first and easy to use techniques for proving run time bounds for
evolutionary algorithms is the so-called method of fitness levels by Wegener.
It uses a partition of the search space into a sequence of levels which are
traversed by the algorithm in increasing order, possibly skipping levels. An
easy, but often strong upper bound for the run time can then be derived by
adding the reciprocals of the probabilities to leave the levels (or upper
bounds for these). Unfortunately, a similarly effective method for proving
lower bounds has not yet been established. The strongest such method, proposed
by Sudholt (2013), requires a careful choice of the viscosity parameters
$\gamma_{i,j}$, $0 \le i < j \le n$.
In this paper we present two new variants of the method, one for upper and
one for lower bounds. Besides the level leaving probabilities, they only rely
on the probabilities that levels are visited at all. We show that these can be
computed or estimated without greater difficulties and apply our method to
reprove the following known results in an easy and natural way. (i) The precise
run time of the \oea on \leadingones. (ii) A lower bound for the run time of
the \oea on \onemax, tight apart from an $O(n)$ term. (iii) A lower bound for
the run time of the \oea on long $k$-paths.
- Abstract（参考訳）: 進化的アルゴリズムのランタイムバウンドを証明するために最初に、そして簡単に使える技術の一つが、Wegenerによるいわゆるフィットネスレベルの方法である。
探索空間の分割を、アルゴリズムによって順に横断される一連のレベルに分割し、おそらくはレベルをスキップする。
実行時間に対する容易だが強固な上界は、確率の逆数を追加してレベル(あるいはそれらの上界)を離れることによって導かれる。
残念ながら、下界を証明する同様の効果的な方法はまだ確立されていない。
sudholt (2013) が提唱した最も強い方法では、粘度パラメータ $\gamma_{i,j}$, $0 \le i < j \le n$ の慎重に選択する必要がある。
本稿では,上界法と下界法という2つの新しい変種について述べる。
レベル離脱確率の他に、彼らはレベルが訪問される確率にのみ依存している。
より困難を伴わない計算や推定が可能であることを示し、本手法を適用して、以下の既知結果を簡単かつ自然な方法で再現する。
i) \leadingones 上の \oea の正確な実行時間。
(ii) \onemax 上の \oea の実行時間に対する低いバウンダリで、$O(n)$ 項とは分離する。
(iii)長い$k$-paths での \oea の実行時間に対する下限。
関連論文リスト
- Stochastic Gradient Succeeds for Bandits [64.17904367852563]
エンフィスト確率勾配帯域幅アルゴリズムは,O (1/t)$レートで,エンフィグロブな最適ポリシに収束することを示す。
興味深いことに、勾配帯域アルゴリズムのグローバル収束は以前に確立されていない。
論文 参考訳（メタデータ） (2024-02-27T06:05:01Z) - Fast Estimations of Hitting Time of Elitist Evolutionary Algorithms from Fitness Levels [4.605031905884542]
そこで我々は, 線形下界と上界を適合度で構築するための新しい有向グラフ(グラフ)法を開発した。
この新しい手法の大きな利点は、ショートカットによるフィットネス関数の厳密な下界の導出である。
我々の研究は、簡単なフィットネス機能にショートカットなしで対処することから、より複雑なショートカット機能まで、フィットネスレベルメソッドを著しく拡張した。
論文 参考訳（メタデータ） (2023-11-17T13:04:42Z) - Drift Analysis with Fitness Levels for Elitist Evolutionary Algorithms [11.335004901064352]
フィットネスレベルから最も厳密な距離境界が構築され、初めて証明される。
異なる種類の線形境界に対する異なる適合度レベル手法の開発に使用できるフレームワークが確立されている。
論文 参考訳（メタデータ） (2023-09-02T07:42:57Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Nearly Optimal Algorithms for Level Set Estimation [21.83736847203543]
線形包帯に対する最近の適応的実験設計手法と関連づけることで, レベルセット推定問題に対する新しいアプローチを提案する。
我々は、我々の境界がほぼ最適であることを示す。すなわち、我々の上限は、しきい値線形帯域に対して既存の下限と一致する。
論文 参考訳（メタデータ） (2021-11-02T17:45:02Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。