論文の概要: A Simplified Run Time Analysis of the Univariate Marginal Distribution
Algorithm on LeadingOnes
- arxiv url: http://arxiv.org/abs/2004.04978v1
- Date: Fri, 10 Apr 2020 10:20:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-14 20:07:44.547942
- Title: A Simplified Run Time Analysis of the Univariate Marginal Distribution
Algorithm on LeadingOnes
- Title（参考訳）: 単変量行列分布アルゴリズムのリードワン上での簡易実行時間解析
- Authors: Benjamin Doerr, Martin Krejca
- Abstract要約: 単変量分布アルゴリズム(UMDA)における実行時間保証の強化を実証する。
より少ない選択率によるランタイムゲインを示す。
同様の仮定の下では、我々の上界と定数因子に一致する境界が高い確率で成り立つことを証明している。
- 参考スコア（独自算出の注目度）: 9.853329403413701
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: With elementary means, we prove a stronger run time guarantee for the
univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes
benchmark function in the desirable regime with low genetic drift. If the
population size is at least quasilinear, then, with high probability, the UMDA
samples the optimum within a number of iterations that is linear in the problem
size divided by the logarithm of the UMDA's selection rate. This improves over
the previous guarantee, obtained by Dang and Lehre (2015) via the deep
level-based population method, both in terms of the run time and by
demonstrating further run time gains from small selection rates. With similar
arguments as in our upper-bound analysis, we also obtain the first lower bound
for this problem. Under similar assumptions, we prove that a bound that matches
our upper bound up to constant factors holds with high probability.
- Abstract（参考訳）: 基本的手法により,遺伝的ドリフトが低い条件下でのLeadingOnesベンチマーク関数を最適化する一変量境界分布アルゴリズム (UMDA) の実行時間を保証する。
集団サイズが少なくとも準線形である場合、UMDAは、UMDAの選択率の対数で分割された問題サイズにおいて線形である複数の反復において、その最適値をサンプリングする。
これは、dangとlehre (2015)によって、実行時間と小さな選択率によるさらなる実行時間の向上を示すことによって、ディープレベルベースの人口法によって得られた以前の保証よりも改善される。
上界解析と同様の議論により、この問題に対する最初の下界も得られる。
同様の仮定の下では、我々の上界と定数因子に一致する境界が高い確率で成り立つことを証明している。
関連論文リスト
- On the Estimation Performance of Generalized Power Method for
Heteroscedastic Probabilistic PCA [21.9585534723895]
我々は,少なくとも幾何的にあるしきい値に束縛されたGPM間の適切な繰り返しを仮定すると,GPMは,ある「相対分解」の残余部分であるしきい値に減少することを示す。
そこで本研究では,PCA手法を用いて,ガウス以下の雑音設定による優れた性能を示す。
論文 参考訳（メタデータ） (2023-12-06T11:41:17Z) - Symmetric Mean-field Langevin Dynamics for Distributional Minimax
Problems [78.96969465641024]
平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。
また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
論文 参考訳（メタデータ） (2023-12-02T13:01:29Z) - Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。
本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
論文 参考訳（メタデータ） (2023-06-27T08:15:28Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳（メタデータ） (2022-10-08T08:26:22Z) - Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
Annealed Importance Smpling (AIS) は、深層生成モデルの難易度を推定するために使われる一般的なアルゴリズムである。
本稿では、フレキシブルな中間分布を持つパラメータAISプロセスを提案し、サンプリングに少ないステップを使用するようにブリッジング分布を最適化する。
我々は, 最適化AISの性能評価を行い, 深部生成モデルの限界推定を行い, 他の推定値と比較した。
論文 参考訳（メタデータ） (2022-09-27T07:58:25Z) - Utilising the CLT Structure in Stochastic Gradient based Sampling :
Improved Analysis and Faster Algorithms [14.174806471635403]
粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。
近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。
この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
論文 参考訳（メタデータ） (2022-06-08T10:17:40Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳（メタデータ） (2021-12-24T17:21:04Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Many-Objective Estimation of Distribution Optimization Algorithm Based
on WGAN-GP [1.2461503242570644]
EDAは多目的最適問題(MOP)をよりよく解決できる
We generate the new population by Wasserstein Generative Adversarial Networks-Gradient Penalty (WGAN-GP)
論文 参考訳（メタデータ） (2020-03-16T03:14:59Z) - An Optimal Multistage Stochastic Gradient Method for Minimax Problems [8.615625517708324]
滑らかかつ強凸な凹凸配置におけるミニマックス最適化問題について検討する。
まず, 定常ステップサイズでグラディエントDescent Ascent (GDA) 法を解析した。
本稿では,学習速度の減衰スケジュールを多段階に設定した多段階型GDAを提案する。
論文 参考訳（メタデータ） (2020-02-13T18:01:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。