論文の概要: Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling
- arxiv url: http://arxiv.org/abs/2407.16936v1
- Date: Wed, 24 Jul 2024 02:15:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-25 15:02:58.584787
- Title: Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling
- Title（参考訳）: 非log-concaveサンプリングにおけるanaled Langevin Monte Carloの確率的ベネフィット
- Authors: Wei Guo, Molei Tao, Yongxin Chen,
- Abstract要約: 簡単なアニール型Langevin Monte Carloアルゴリズムに対して$widetildeOleft(fracdbeta2cal A2varepsilon6right)のオラクル複雑性を確立する。
例えば、$cal A$ は対象分布 $pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
- 参考スコア（独自算出の注目度）: 28.931489333515618
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We address the outstanding problem of sampling from an unnormalized density that may be non-log-concave and multimodal. To enhance the performance of simple Markov chain Monte Carlo (MCMC) methods, techniques of annealing type have been widely used. However, quantitative theoretical guarantees of these techniques are under-explored. This study takes a first step toward providing a non-asymptotic analysis of annealed MCMC. Specifically, we establish, for the first time, an oracle complexity of $\widetilde{O}\left(\frac{d\beta^2{\cal A}^2}{\varepsilon^6}\right)$ for simple annealed Langevin Monte Carlo algorithm to achieve $\varepsilon^2$ accuracy in Kullback-Leibler divergence to the target distribution $\pi\propto{\rm e}^{-V}$ on $\mathbb{R}^d$ with $\beta$-smooth potential $V$. Here, ${\cal A}$ represents the action of a curve of probability measures interpolating the target distribution $\pi$ and a readily sampleable distribution.
- Abstract（参考訳）: 非log-concave および multimodal である可能性のある非正規化密度からのサンプリングの問題に対処する。
単純なマルコフ連鎖モンテカルロ法 (MCMC) の性能を高めるため, 焼鈍型法が広く用いられている。
しかし、これらの手法の定量的な保証は未発見である。
本研究は、焼鈍MCMCの非漸近解析を提供するための第一歩となる。
具体的には、まず最初のオラクル複雑性を$\widetilde{O}\left(\frac{d\beta^2{\cal A}^2}{\varepsilon^6}\right)$で確立し、単純なアンニールランジェヴィン・モンテカルロアルゴリズムにより、ターゲット分布へのKullback-Leibler分散の精度を$\pi\propto{\rm e}^{-V}$で$\mathbb{R}^d$で$\beta$-smooth potential $V$とする。
ここで、${\cal A}$ は対象分布 $\pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
関連論文リスト
- Langevin Quasi-Monte Carlo [6.146093081175471]
ランゲヴィン・モンテカルロ(LMC)とその勾配バージョンは複雑な高次元分布からサンプリングする強力なアルゴリズムである。
準ランダムサンプルを用いてLCCの推定誤差を低減できることを示す。
論文 参考訳（メタデータ） (2023-09-22T07:15:18Z) - Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
我々は、強化学習のためのトンプソンサンプリングに基づくスケーラブルで効果的な探索戦略を提案する。
代わりに、Langevin Monte Carlo を用いて、Q 関数をその後部分布から直接サンプリングする。
提案手法は,Atari57スイートからのいくつかの挑戦的な探索課題において,最先端の深部RLアルゴリズムと比較して,より優れた,あるいは類似した結果が得られる。
論文 参考訳（メタデータ） (2023-05-29T17:11:28Z) - Faster high-accuracy log-concave sampling via algorithmic warm starts [6.117084972237769]
実際には、古典的なメトロポリス調整ランゲヴィンアルゴリズム(MALA)のような高精度なサンプリング器は事実上のゴールド標準のままである。
我々は,このサンプリング問題の次元依存性を$tildeO(d1/2)$に改善し,MALAでは$tildeO(d1/2)$とした。
我々の主な技術的貢献は、離散化アンダーダム化ランゲヴィン拡散に対する最初の$tildeO(d1/2)$ R'enyi混合速度を確立することでこの問題を解決することである。
論文 参考訳（メタデータ） (2023-02-20T19:27:21Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity
Guarantees for Langevin Monte Carlo [24.00911089902082]
これは$mathdで$pi exp(-V)$を見つけるためのサンプリングイテレーションである。
多数の拡張応用について論じ、特に非凹凸サンプリングの一般理論への第一歩である。
論文 参考訳（メタデータ） (2022-02-10T18:20:55Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。
特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
論文 参考訳（メタデータ） (2020-07-22T18:18:28Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。