論文の概要: Faster Optimization Through Genetic Drift

• arxiv url: http://arxiv.org/abs/2404.12147v1
• Date: Thu, 18 Apr 2024 12:51:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-19 12:31:46.717121
• Title: Faster Optimization Through Genetic Drift
• Title（参考訳）: 遺伝的ドリフトによる高速最適化
• Authors: Cella Florescu, Marc Kaufmann, Johannes Lengler, Ulysse Schaller,
• Abstract要約: 遺伝的アルゴリズム(cGA)は、大規模な子孫のソリューションを進化させるための低メモリの代替手段を提供する。 我々は、OneMaxをより難しい丘登り問題であるDynamicBinValに置き換えると、両者がどう変化するかを研究する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The compact Genetic Algorithm (cGA), parameterized by its hypothetical population size $K$, offers a low-memory alternative to evolving a large offspring population of solutions. It evolves a probability distribution, biasing it towards promising samples. For the classical benchmark OneMax, the cGA has to two different modes of operation: a conservative one with small step sizes $\Theta(1/(\sqrt{n}\log n))$, which is slow but prevents genetic drift, and an aggressive one with large step sizes $\Theta(1/\log n)$, in which genetic drift leads to wrong decisions, but those are corrected efficiently. On OneMax, an easy hill-climbing problem, both modes lead to optimization times of $\Theta(n\log n)$ and are thus equally efficient. In this paper we study how both regimes change when we replace OneMax by the harder hill-climbing problem DynamicBinVal. It turns out that the aggressive mode is not affected and still yields quasi-linear runtime $O(n\cdot polylog (n))$. However, the conservative mode becomes substantially slower, yielding a runtime of $\Omega(n^2)$, since genetic drift can only be avoided with smaller step sizes of $O(1/n)$. We complement our theoretical results with simulations.
• Abstract（参考訳）: コンパクト遺伝的アルゴリズム(cGA)は、その仮想的な集団サイズ$K$でパラメータ化され、大きな子孫の解を進化させるための低メモリの代替手段を提供する。 確率分布を進化させ、有望なサンプルに偏りを与える。 古典的なベンチマークであるOneMaxでは、cGAには2つの異なる操作モードがある: 小さなステップサイズを持つ保守的な1つ$\Theta(1/(\sqrt{n}\log n))$、大きなステップサイズを持つ攻撃的な1つ$\Theta(1/\log n)$。 簡単なヒルクライミング問題であるOneMaxでは、どちらのモードも$\Theta(n\log n)$の最適化時間につながり、したがって等しく効率的である。 本稿では,OneMaxに代えて,より難しい丘登上問題であるDynamicBinValで両制度がどう変化するかを検討する。 その結果、アグレッシブモードは影響を受けず、準線形ランタイムである$O(n\cdot polylog (n))$を引き続き得ることがわかった。 しかし、保守モードは著しく遅くなり、遺伝的ドリフトはO(1/n)$より小さいステップサイズでしか回避できないため、$\Omega(n^2)$のランタイムが得られる。 我々は理論結果をシミュレーションで補完する。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。 本手法の主な考え方は,状況認識による$alphaの適応である。 これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
  論文  参考訳（メタデータ） (2023-09-12T14:36:13Z)
• Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm [7.421135890148154]
  集団サイズが$mu=O(n)$の遺伝的アルゴリズムは、ギャップサイズが$k ge 3$のジャンプ関数を最適化する。 この多様性は、(二次的ではなく)$mu$で指数関数的に高い確率で持続することを示す。 すべての$cln(n)lemu le n/log n$, with $c$ a suitable constant, the runtime of the $(mu+1)$ GA on $mathrmJump_k$, with $k
  論文  参考訳（メタデータ） (2023-02-24T10:50:24Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• No quantum speedup over gradient descent for non-smooth convex optimization [22.16973542453584]
  ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。 私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。 下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
  論文  参考訳（メタデータ） (2020-10-05T06:32:47Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization [33.346773349614715]
  本報告では,NonpsOmegaのための新しい確率勾配エストリマト(フラスト)を提案する。 小さなPAGEからバニラSGDへと設計されているため、実装が容易である。 トレーニングにおいてSGDよりもはるかに早く収束するだけでなく、高い精度を達成する。
  論文  参考訳（メタデータ） (2020-08-25T09:11:31Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。 我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。 トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
  論文  参考訳（メタデータ） (2020-06-28T04:37:57Z)
• Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax [1.0965065178451106]
  我々は、最適な突然変異率の分析を、OneMax問題の2つの変種に拡張する。 すべての集団サイズを2i mid 0 le i le 18$で計算します。 我々の結果は、一般的な進化的アプローチを測ることのできる低い境界を提供するばかりではない。
  論文  参考訳（メタデータ） (2020-06-20T01:23:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。