Fugu-MT 論文翻訳(概要): The Runtime of Random Local Search on the Generalized Needle Problem

論文の概要: The Runtime of Random Local Search on the Generalized Needle Problem

arxiv url: http://arxiv.org/abs/2403.08153v2
Date: Wed, 20 Mar 2024 00:18:40 GMT
ステータス: 処理完了
システム内更新日: 2024-03-21 21:18:47.911575
Title: The Runtime of Random Local Search on the Generalized Needle Problem
Title（参考訳）: 一般化針問題におけるランダム局所探索の実行
Authors: Benjamin Doerr, Andrew James Kelley,
Abstract要約: 我々は、C. Doerr と Krejca が与えられた上限を大幅に改善する期待ランタイムの正確な記述を導出する。また、期待されるランタイムの推定についても記述する。
参考スコア（独自算出の注目度）: 10.165640083594573
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In their recent work, C. Doerr and Krejca (Transactions on Evolutionary Computation, 2023) proved upper bounds on the expected runtime of the randomized local search heuristic on generalized Needle functions. Based on these upper bounds, they deduce in a not fully rigorous manner a drastic influence of the needle radius $k$ on the runtime. In this short article, we add the missing lower bound necessary to determine the influence of parameter $k$ on the runtime. To this aim, we derive an exact description of the expected runtime, which also significantly improves the upper bound given by C. Doerr and Krejca. We also describe asymptotic estimates of the expected runtime.
Abstract（参考訳）: 最近の研究で、C. Doerr と Krejca (2023年) は、一般化されたニードル関数上のランダム化された局所探索ヒューリスティックの予想ランタイム上の上限を証明した。これらの上限に基づいて、それらは実行時における針半径$k$の劇的な影響を、完全に厳密でない方法で推論する。この記事では、実行時に$k$のパラメータの影響を決定するのに必要な、不足している低いバウンダリを追加します。この目的のために、期待されるランタイムの正確な記述を導き、C. Doerr と Krejca によって与えられる上限を大幅に改善する。また,予測ランタイムの漸近的推定についても述べる。

関連論文リスト

Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
論文参考訳（メタデータ） (2024-04-03T00:41:19Z)
Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
論文参考訳（メタデータ） (2024-04-02T16:35:52Z)
Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。最後に,提案手法に適用可能な最終収束率を導出する。
論文参考訳（メタデータ） (2023-12-02T07:12:00Z)
Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar\'e Inequality [15.941909642134085]
この研究プログラムは、ログソボレフの不等式で結果を確立したベンパラとウィビソノによって始められた。この結果は,初期化器がLangevin Monte Carlo (LMC) アルゴリズムの性能に与える影響を明示的に定量化する。
論文参考訳（メタデータ） (2023-03-07T01:45:04Z)
Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
既存の一般化境界は、現代のニューラルネットワークの一般化を促進する重要な要因を説明することができない。データ空間における学習予測関数の局所リプシッツ正則性に依存するインスタンス依存の一般化境界を導出する。ニューラルネットワークに対する一般化境界を実験的に解析し、有界値が有意義であることを示し、トレーニング中の一般的な正規化方法の効果を捉える。
論文参考訳（メタデータ） (2022-11-02T16:39:42Z)
Resolution Limits of Non-Adaptive 20 Questions Search for a Moving Target [8.767398758618793]
本研究では,初期位置と速度の不明な単位立方体上での移動対象の非適応探索戦略を,一様定速度モデルの下で検討する。非漸近的および有界性を導出することにより、最適な非適応的クエリ手順の最小解を有限個のクエリで特徴付ける。この結果を証明するために、チャネル符号化、有限ブロック長情報理論からのアイデアの借用、および量子化された対象軌道の数に基づく構成境界について、現状の問題点を考察する。
論文参考訳（メタデータ） (2022-06-14T02:20:05Z)
Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
我々は,高次元ロバストな統計問題を解くためにGAN(Generative Adversarial Networks)を設計するためのフレームワークを提供する。我々の研究は、これらをロバスト平均推定、第二モーメント推定、ロバスト線形回帰に拡張する。技術面では、提案したGAN損失は、スムーズで一般化されたコルモゴロフ-スミルノフ距離と見なすことができる。
論文参考訳（メタデータ） (2022-02-02T20:11:33Z)
Minimax Kernel Machine Learning for a Class of Doubly Robust Functionals [16.768606469968113]
もともと導入された二重頑健なモーメント関数のクラスを考える(Robins et al., 2008)。このモーメント関数は、ニュアンス関数の推定方程式の構築に使用できることを実証する。ニュアンス関数の収束速度は、統計学習理論の現代的な手法を用いて解析される。
論文参考訳（メタデータ） (2021-04-07T05:52:15Z)
An Analysis of the Adaptation Speed of Causal Models [80.77896315374747]
最近、Bengioらは、すべての候補モデルの中で、$G$は、あるデータセットから別のデータセットに適応する最速のモデルであると推測した。最適化からの収束率を用いた原因影響SCMの適応速度について検討する。驚くべきことに、私たちは反因果モデルが有利である状況を見つけ、初期仮説を偽造する。
論文参考訳（メタデータ） (2020-05-18T23:48:56Z)

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