論文の概要: Exponential Upper Bounds for the Runtime of Randomized Search Heuristics
- arxiv url: http://arxiv.org/abs/2004.05733v4
- Date: Sat, 9 Oct 2021 17:04:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-13 23:33:57.457122
- Title: Exponential Upper Bounds for the Runtime of Randomized Search Heuristics
- Title（参考訳）: ランダム化探索ヒューリスティックのランタイムに対する指数上限
- Authors: Benjamin Doerr
- Abstract要約: アルゴリズムの任意のランダム化ローカルサーチ,アルゴリズム,シミュレートされたアニーリング,および (1+1) 進化的アルゴリズムが,任意の擬ブール弱単調関数を最適化可能であることを示す。
また、OneMaxベンチマークにおいて、単純な遺伝的アルゴリズムの突然変異に基づくバージョンの実行時の指数的な上限を証明した。
- 参考スコア（独自算出の注目度）: 9.853329403413701
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We argue that proven exponential upper bounds on runtimes, an established
area in classic algorithms, are interesting also in heuristic search and we
prove several such results. We show that any of the algorithms randomized local
search, Metropolis algorithm, simulated annealing, and (1+1) evolutionary
algorithm can optimize any pseudo-Boolean weakly monotonic function under a
large set of noise assumptions in a runtime that is at most exponential in the
problem dimension~$n$. This drastically extends a previous such result, limited
to the (1+1) EA, the LeadingOnes function, and one-bit or bit-wise prior noise
with noise probability at most $1/2$, and at the same time simplifies its
proof. With the same general argument, among others, we also derive a
sub-exponential upper bound for the runtime of the $(1,\lambda)$ evolutionary
algorithm on the OneMax problem when the offspring population size $\lambda$ is
logarithmic, but below the efficiency threshold. To show that our approach can
also deal with non-trivial parent population sizes, we prove an exponential
upper bound for the runtime of the mutation-based version of the simple genetic
algorithm on the OneMax benchmark, matching a known exponential lower bound.
- Abstract（参考訳）: 古典的アルゴリズムの確立された領域であるランタイムの指数的上限は、ヒューリスティック検索においても興味深いものであり、いくつかの結果が証明されている。
各アルゴリズムのランダム化局所探索,メトロポリスアルゴリズム,シミュレートアニーリング,および (1+1) 進化アルゴリズムは,問題次元~n$ において最大指数関数であるランタイム内の大きな雑音仮定の下で任意の疑似ボアの弱単調関数を最適化できることを示す。
これは、(1+1) ea、leadingones関数、およびノイズ確率が最大1/2$の1ビットまたはビット単位の事前ノイズに制限され、同時にその証明を単純化する以前の結果を大幅に拡張する。
同じ一般論法で、例えば1,\lambda)$1Max問題において、子孫の集団サイズ$\lambda$が対数であるが効率しきい値以下である場合の1,\lambda)$進化アルゴリズムのランタイムに対する部分指数上界も導出する。
提案手法は,非自明な親集団サイズも扱えることを示すため,OneMaxベンチマークにおいて,単純な遺伝的アルゴリズムの突然変異に基づくバージョンの実行時の指数上界を,既知の指数下界と一致させて証明する。
関連論文リスト
- Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。
この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文 参考訳（メタデータ） (2024-04-02T16:35:52Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic
Algorithm to Overcome the Noise [76.24156145566425]
進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。
我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
論文 参考訳（メタデータ） (2023-05-08T08:49:01Z) - 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) - Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。
O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。
さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
論文 参考訳（メタデータ） (2021-10-15T00:54:04Z) - Classical algorithms and quantum limitations for maximum cut on
high-girth graphs [6.262125516926276]
すべての(量子または古典的な)一局所アルゴリズムが$D$正規グラフに対して$5$の最大カットが1/2 + C/sqrtD$ for $C=1/sqrt2 approx 0.7071$であることを示す。
1/2 + C/sqrtD - O (1/sqrtk)$ for $D$-regular graphs of $> 2k+1$,
論文 参考訳（メタデータ） (2021-06-10T16:28:23Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Lower Bounds for Non-Elitist Evolutionary Algorithms via Negative
Multiplicative Drift [9.853329403413701]
乗法的ドリフトシナリオに対する単純な負のドリフト定理は既存の解析を単純化できることを示す。
我々は、非エリート変異に基づく進化アルゴリズムのランタイムにおける下位境界を証明するための最も一般的なツールの1つである集団法において、Lehre's emph negative drift in populations法(PPSN 2010)についてより詳細に論じる。
論文 参考訳（メタデータ） (2020-05-02T15:10:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。