論文の概要: Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions

• arxiv url: http://arxiv.org/abs/2106.05480v1
• Date: Thu, 10 Jun 2021 03:47:39 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-12 20:44:17.288388
• Title: Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
• Title（参考訳）: 十分条件分布のメトロポレートサンプリング法における下限
• Authors: Yin Tat Lee, Ruoqi Shen, Kevin Tian
• Abstract要約: 我々は、実際に最もポピュラーなサンプリング手法であるランゲヴィンアルゴリズム(MALA)とマルチステップのハミルトンモンテカルロ(HMC)の2つの性能に低い限界を与える。 我々の主な結果は、指数的に暖かい開始からMALAの混合時間における$widetildeOmega(kappa d)$のほぼ28の低い境界である。
• 参考スコア（独自算出の注目度）: 29.314919044203926
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give lower bounds on the performance of two of the most popular sampling methods in practice, the Metropolis-adjusted Langevin algorithm (MALA) and multi-step Hamiltonian Monte Carlo (HMC) with a leapfrog integrator, when applied to well-conditioned distributions. Our main result is a nearly-tight lower bound of $\widetilde{\Omega}(\kappa d)$ on the mixing time of MALA from an exponentially warm start, matching a line of algorithmic results up to logarithmic factors and answering an open question of Chewi et. al. We also show that a polynomial dependence on dimension is necessary for the relaxation time of HMC under any number of leapfrog steps, and bound the gains achievable by changing the step count. Our HMC analysis draws upon a novel connection between leapfrog integration and Chebyshev polynomials, which may be of independent interest.
• Abstract（参考訳）: 我々は,よく調和した分布に適用した場合,最も一般的なサンプリング手法であるメトロポリス調整ランゲヴィンアルゴリズム (MALA) と,跳躍フロッグ積分器を用いたマルチステップハミルトンモンテカルロ (HMC) の性能を低くする。 私たちの主な結果は、指数関数的に温かいスタートからmalaの混合時間に関する$\widetilde{\omega}(\kappa d)$のほぼタイトな下限であり、アルゴリズム的な結果のラインを対数因子に一致させ、chewi etのオープン質問に答えます。 アル また, HMC の任意の段数における緩和時間には, 次元への多項式依存が必要であり, ステップ数を変化させることで得られるゲインを束縛できることも示している。 我々のHMC分析は、跳躍積分とチェビシェフ多項式の間の新しい関係を導いており、これは独立した関心を持つかもしれない。

関連論文リスト

• Near-Optimal Learning and Planning in Separated Latent MDPs [70.88315649628251]
  我々は、潜在マルコフ決定過程(LMDP)の計算的および統計的側面について研究する。 このモデルでは、学習者は、未知のMDPの混合から各エポックの開始時に描画されたMDPと相互作用する。
  論文  参考訳（メタデータ） (2024-06-12T06:41:47Z)
• Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo [30.4930148381328]
  拡散に基づくモンテカルロ (DMC) は、等尺条件を超えた一般目標分布から試料を採取する手法である。 DMCは、高い勾配の複雑さに遭遇し、その結果、得られたサンプルのエラー耐性$epsilon$に指数関数的に依存する。 本稿では,新しい再帰に基づくスコア推定法に基づくRS-DMCを提案する。 私たちのアルゴリズムは、人気のあるLangevinベースのアルゴリズムよりもはるかに高速です。
  論文  参考訳（メタデータ） (2024-01-12T02:33:57Z)
• Symmetric Mean-field Langevin Dynamics for Distributional Minimax Problems [78.96969465641024]
  平均場ランゲヴィンのダイナミクスを、対称で証明可能な収束した更新で、初めて確率分布に対する最小の最適化に拡張する。 また,時間と粒子の離散化機構について検討し,カオス結果の新たな均一時間伝播を証明した。
  論文  参考訳（メタデータ） (2023-12-02T13:01:29Z)
• When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm? [4.657614491309671]
  本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。 連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
  論文  参考訳（メタデータ） (2023-04-10T17:35:57Z)
• Improved Bound for Mixing Time of Parallel Tempering [4.68299658663016]
  パラレルテンパリングのための新しい下限を、$log L$を除く全てのパラメータにマルチモーダル依存を持つスペクトルギャップ上で提示する。 これにより、モードの数に指数関数的に依存する最良の既存の境界が改善される。 スペクトルギャップ上の仮定上界は$log L$に指数関数依存しており、ある意味では我々の境界は密であることを示す。
  論文  参考訳（メタデータ） (2023-04-03T19:03:22Z)
• Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods [35.24886589614034]
  一般相互作用が$J$である超キューブ上の二次定値イジングモデルを考える。 我々の一般的な結果は、低ランクのIsingモデルに対する最初のサンプリングアルゴリズムを示唆している。
  論文  参考訳（メタデータ） (2022-02-17T21:43:50Z)
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond [63.59034509960994]
  シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
  論文  参考訳（メタデータ） (2021-10-20T02:25:25Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo [1.14219428942199]
  私たちは、調整されていないハミルトンモンテカルロ(uHMC)アルゴリズムに対応するマルコフ鎖の総変動混合時間に関する定量的な上限を提供します。 2つの一般的なモデルのクラスと固定時間離散化ステップサイズ$h$ に対して、混合時間は次元に対数的にのみ依存することが示される。 UHMCにより,目標分布の精度を$varepsilon$-accurate approximation of the target distribution $mu$ in total variation distanceを実現できることを示す。
  論文  参考訳（メタデータ） (2021-05-03T14:13:47Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  ハイブリッドモンテカルロ(Hybrid Monte Carlo)は、複素連続分布からサンプリングする強力なマルコフ連鎖モンテカルロ法である。 本稿では,SurVAEフローを用いたモンテカルロ法の拡張に基づく新しい手法を提案する。 本稿では,統計学,計算物理学,機械学習など,様々な分野におけるアルゴリズムの有効性を実証し,代替アルゴリズムと比較した改良点を考察する。
  論文  参考訳（メタデータ） (2021-02-04T02:21:08Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。 一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
  論文  参考訳（メタデータ） (2020-04-09T17:54:18Z)

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

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