論文の概要: Fixed-Parameter Tractability of the (1+1) Evolutionary Algorithm on Random Planted Vertex Covers
- arxiv url: http://arxiv.org/abs/2409.10144v1
- Date: Mon, 16 Sep 2024 10:14:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-17 16:00:03.472789
- Title: Fixed-Parameter Tractability of the (1+1) Evolutionary Algorithm on Random Planted Vertex Covers
- Title（参考訳）: ランダム植立頂点被覆上の(1+1)進化アルゴリズムの固定パラメータトラクタビリティ
- Authors: Jack Kearney, Frank Neumann, Andrew M. Sutton,
- Abstract要約: カバー問題の分布に関する標準 (1+1) アルゴリズムの最初のパラメータ化解析について述べる。
植木カバーが少なくとも対数的であれば、$(n log n)$のステップ毎に (1+1) EA が再起動すると、植木カバーの時間における最小限のカバーが見つかる。
- 参考スコア（独自算出の注目度）: 9.399996222083587
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every $O(n \log n)$ steps will find a cover at least as small as the planted cover in polynomial time for sufficiently dense random graphs $p > 0.71$. For superlogarithmic planted covers, we prove that the (1+1) EA finds a solution in fixed-parameter tractable time in expectation. We complement these theoretical investigations with a number of computational experiments that highlight the interplay between planted cover size, graph density and runtime.
- Abstract（参考訳）: 本稿では,頂点被覆問題の分布に関する標準 (1+1) 進化的アルゴリズムの最初のパラメータ化解析について述べる。
植込み被覆が少なくとも対数的であれば、 (1+1) EA を $O(n \log n)$ ステップごとに再起動すると、十分に密集したランダムグラフに対して多項式時間で植込み被覆が少なくとも小さいカバーを見つけることが示される。
超対数被覆の場合、(1+1) EA が期待される固定パラメータのトラクタブル時間で解を見つけることが証明される。
我々はこれらの理論的研究を、植込みカバーサイズ、グラフ密度、実行時の相互作用を強調する多くの計算実験で補完する。
関連論文リスト
- Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳（メタデータ） (2024-02-01T03:39:01Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳（メタデータ） (2022-04-06T13:50:33Z) - Focused Jump-and-Repair Constraint Handling for Fixed-Parameter
Tractable Graph Problems Closed Under Induced Subgraphs [3.495114525631289]
グラフ問題における不可能な子孫の確率的修復に使用できる調整されたジャンプ・アンド・リペア操作を備えた(1+1)EAについて検討する。
論文 参考訳（メタデータ） (2022-03-25T19:36:02Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Improved Runtime Results for Simple Randomised Search Heuristics on
Linear Functions with a Uniform Constraint [11.228244128564512]
均一制約下での線形関数のクラスについて検討し、ランダム化局所探索(RLS)の期待最適時間について検討する。
RLS に対して $Theta(n2)$ の厳密な境界を証明し、(1+1) EA の既知上界を改善する。
論文 参考訳（メタデータ） (2020-10-21T10:42:39Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳（メタデータ） (2020-06-24T06:01:24Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - A new regret analysis for Adam-type algorithms [78.825194932103]
理論的には、オンライン凸最適化に対する後悔の保証は、急速に崩壊する$beta_1to0$スケジュールを必要とする。
最適なデータ依存リセット境界を一定の$beta_1$で導出できる新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-21T19:19:51Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。