論文の概要: Optimal Scaling for Locally Balanced Proposals in Discrete Spaces

• arxiv url: http://arxiv.org/abs/2209.08183v1
• Date: Fri, 16 Sep 2022 22:09:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-20 18:45:07.270465
• Title: Optimal Scaling for Locally Balanced Proposals in Discrete Spaces
• Title（参考訳）: 離散空間における局所平衡提案の最適スケーリング
• Authors: Haoran Sun, Hanjun Dai, Dale Schuurmans
• Abstract要約: 離散空間におけるMetropolis-Hastings (M-H) アルゴリズムの効率は、対象分布に依存しない受容率によって特徴づけられることを示す。 最適受容率の知識は、連続空間におけるステップサイズ制御と直接的に類似して、離散空間における提案分布の近傍サイズを自動的に調整することを可能にする。
• 参考スコア（独自算出の注目度）: 65.14092237705476
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal scaling has been well studied for Metropolis-Hastings (M-H) algorithms in continuous spaces, but a similar understanding has been lacking in discrete spaces. Recently, a family of locally balanced proposals (LBP) for discrete spaces has been proved to be asymptotically optimal, but the question of optimal scaling has remained open. In this paper, we establish, for the first time, that the efficiency of M-H in discrete spaces can also be characterized by an asymptotic acceptance rate that is independent of the target distribution. Moreover, we verify, both theoretically and empirically, that the optimal acceptance rates for LBP and random walk Metropolis (RWM) are $0.574$ and $0.234$ respectively. These results also help establish that LBP is asymptotically $O(N^\frac{2}{3})$ more efficient than RWM with respect to model dimension $N$. Knowledge of the optimal acceptance rate allows one to automatically tune the neighborhood size of a proposal distribution in a discrete space, directly analogous to step-size control in continuous spaces. We demonstrate empirically that such adaptive M-H sampling can robustly improve sampling in a variety of target distributions in discrete spaces, including training deep energy based models.
• Abstract（参考訳）: 最適スケーリングは連続空間におけるmetropolis-hastings (m-h)アルゴリズムでよく研究されてきたが、離散空間では同様の理解が欠けている。 近年、離散空間に対する局所均衡提案(lbp)の族は漸近的に最適であることが証明されているが、最適スケーリングの問題は未解決である。 本稿では, 離散空間におけるM-Hの効率性は, 対象分布に依存しない漸近的受容率によっても特徴付けられることを示す。 さらに, lbpとランダムウォークメトロポリス (rwm) の最適受入率は, それぞれ$0.574$と$0.234$であることが理論的および実証的に検証された。 これらの結果は、LBP がモデル次元 $N$ に関して RWM よりも漸近的に $O(N^\frac{2}{3})$ であることを示すのに役立つ。 最適受容率の知識により、離散空間における提案分布の近傍サイズを自動的に調整することができ、連続空間におけるステップサイズ制御と直接似ている。 このような適応的なM-Hサンプリングは、深部エネルギーモデルを含む離散空間における様々なターゲット分布のサンプリングを堅牢に改善できることを示す。

関連論文リスト

• Faster Sampling via Stochastic Gradient Proximal Sampler [28.422547264326468]
  非log-concave分布からのサンプリングのための近位サンプリング器 (SPS) について検討した。 対象分布への収束性は,アルゴリズムの軌道が有界である限り保証可能であることを示す。 我々は、Langevin dynamics(SGLD)とLangevin-MALAの2つの実装可能な変種を提供し、SPS-SGLDとSPS-MALAを生み出した。
  論文  参考訳（メタデータ） (2024-05-27T00:53:18Z)
• Broadening Target Distributions for Accelerated Diffusion Models via a Novel Analysis Approach [49.97755400231656]
  本研究では,新しいDDPMサンプリング器が,これまで考慮されていなかった3種類の分散クラスに対して高速化性能を実現することを示す。 この結果から, DDPM型加速サンプリング器におけるデータ次元$d$への依存性が改善された。
  論文  参考訳（メタデータ） (2024-02-21T16:11:47Z)
• Space-Time Diffusion Bridge [0.4527270266697462]
  実確率分布から独立かつ同一に分布する新しい合成サンプルを生成する方法を提案する。 時空間次元にまたがる時空間混合戦略を用いる。 数値実験による時空拡散法の有効性を検証した。
  論文  参考訳（メタデータ） (2024-02-13T23:26:11Z)
• 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)
• Optimal design of the Barker proposal and other locally-balanced Metropolis-Hastings algorithms [0.2148535041822524]
  We study the class of first-order local- Balanced Metropolis--Hastings algorithm introduced in Livingstone & Zanella (2021) クラス内で特定のアルゴリズムを選択するには、ユーザは、$g(t) = tg (1/t)$を満たすバランス関数 $g:mathbbR to mathbbR$と、提案のためのノイズ分布を選択する必要がある。 ベイカー提案における雑音分布の最適選択、ガウス雑音分布下でのバランス関数の最適選択、一階局所バランスアルゴリズムの最適選択を導出する。
  論文  参考訳（メタデータ） (2022-01-04T13:06:50Z)
• LSB: Local Self-Balancing MCMC in Discrete Spaces [2.385916960125935]
  本研究は、純粋に離散的な領域におけるサンプリング効率を向上させるために、機械学習を用いて提案された分布をターゲットに適応させることを検討する。 得られたサンプルをLSB(Locally Self-Balancing Sampler)と呼ぶ。
  論文  参考訳（メタデータ） (2021-09-08T18:31:26Z)
• Variational Refinement for Importance Sampling Using the Forward Kullback-Leibler Divergence [77.06203118175335]
  変分推論(VI)はベイズ推論における正確なサンプリングの代替として人気がある。 重要度サンプリング(IS)は、ベイズ近似推論手順の推定を微調整し、偏りを逸脱するためにしばしば用いられる。 近似ベイズ推論のための最適化手法とサンプリング手法の新たな組み合わせを提案する。
  論文  参考訳（メタデータ） (2021-06-30T11:00:24Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  カーネル平均埋め込みは、その無限次元平均埋め込みによる確率測度を表す。 カーネルが特徴的である場合、カーネルの総和密度を持つ分布は密度が高いことを示す。 有限サンプル設定でそのような分布を最適化するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-06-18T08:33:45Z)
• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm [22.19906823739798]
  ログスムースと強くログ凹分布のクラス上のMALAの混合時間は$O(d)$です。 メトロポリタン調整の投影特性に基づく新しい技術は、ランゲビンSDEのよく研究された離散分析にMALAの研究を減少させる。
  論文  参考訳（メタデータ） (2020-12-23T17:14:06Z)

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

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