論文の概要: Optimal design of the Barker proposal and other locally-balanced
Metropolis-Hastings algorithms
- arxiv url: http://arxiv.org/abs/2201.01123v1
- Date: Tue, 4 Jan 2022 13:06:50 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-05 16:45:04.516534
- Title: Optimal design of the Barker proposal and other locally-balanced
Metropolis-Hastings algorithms
- Title（参考訳）: Barker提案と他の局所平衡メトロポリス・ハスティングスアルゴリズムの最適設計
- Authors: Jure Vogrinc, Samuel Livingstone and Giacomo Zanella
- Abstract要約: 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$と、提案のためのノイズ分布を選択する必要がある。
ベイカー提案における雑音分布の最適選択、ガウス雑音分布下でのバランス関数の最適選択、一階局所バランスアルゴリズムの最適選択を導出する。
- 参考スコア（独自算出の注目度）: 0.2148535041822524
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the class of first-order locally-balanced Metropolis--Hastings
algorithms introduced in Livingstone & Zanella (2021). To choose a specific
algorithm within the class the user must select a balancing function
$g:\mathbb{R} \to \mathbb{R}$ satisfying $g(t) = tg(1/t)$, and a noise
distribution for the proposal increment. Popular choices within the class are
the Metropolis-adjusted Langevin algorithm and the recently introduced Barker
proposal. We first establish a universal limiting optimal acceptance rate of
57% and scaling of $n^{-1/3}$ as the dimension $n$ tends to infinity among all
members of the class under mild smoothness assumptions on $g$ and when the
target distribution for the algorithm is of the product form. In particular we
obtain an explicit expression for the asymptotic efficiency of an arbitrary
algorithm in the class, as measured by expected squared jumping distance. We
then consider how to optimise this expression under various constraints. We
derive an optimal choice of noise distribution for the Barker proposal, optimal
choice of balancing function under a Gaussian noise distribution, and optimal
choice of first-order locally-balanced algorithm among the entire class, which
turns out to depend on the specific target distribution. Numerical simulations
confirm our theoretical findings and in particular show that a bi-modal choice
of noise distribution in the Barker proposal gives rise to a practical
algorithm that is consistently more efficient than the original Gaussian
version.
- Abstract（参考訳）: リビングストン・アンド・ザネラ(英語版) (2021) で導入された一階の局所均衡メトロポリス-ハスティングアルゴリズムのクラスについて検討した。
クラス内で特定のアルゴリズムを選択するには、ユーザーはバランス関数 $g:\mathbb{R} \to \mathbb{R}$ を満足する $g(t) = tg(1/t)$ と、提案インクリメントのノイズ分布を選択する必要がある。
クラス内の一般的な選択は、メトロポリス調整ランゲヴィンアルゴリズムと最近導入されたバーカーの提案である。
まず57%の普遍的限界最適受入率を確立し、n$の次元は、g$の穏やかな滑らかさの仮定の下で、そしてアルゴリズムのターゲット分布が製品形式である場合、クラス全体の無限大になりがちであるとして、n^{-1/3}$をスケーリングする。
特に,クラス内の任意のアルゴリズムの漸近効率の明示的な式を,期待される2乗跳躍距離で測定する。
次に,この表現を様々な制約の下で最適化する方法を検討する。
本稿では,バーカー提案における雑音分布の最適選択,ガウス雑音分布下でのバランス関数の最適選択,およびクラス全体の一階局所バランスアルゴリズムの最適選択を導出する。
数値シミュレーションにより理論的な知見が確認され,特にbarker提案における雑音分布のバイモーダル選択は,ガウシアン版よりも一貫して効率的であることを示す。
関連論文リスト
- Semi-Bandit Learning for Monotone Stochastic Optimization [20.776114616154242]
モノトーン」問題のクラスに対して汎用的なオンライン学習アルゴリズムを提供する。
我々のフレームワークは、預言者、Pandoraのボックスナップサック、不等式マッチング、部分モジュラー最適化など、いくつかの基本的な最適化問題に適用できる。
論文 参考訳（メタデータ） (2023-12-24T07:46:37Z) - Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳（メタデータ） (2023-11-21T18:50:38Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Optimal Scaling for Locally Balanced Proposals in Discrete Spaces [65.14092237705476]
離散空間におけるMetropolis-Hastings (M-H) アルゴリズムの効率は、対象分布に依存しない受容率によって特徴づけられることを示す。
最適受容率の知識は、連続空間におけるステップサイズ制御と直接的に類似して、離散空間における提案分布の近傍サイズを自動的に調整することを可能にする。
論文 参考訳（メタデータ） (2022-09-16T22:09:53Z) - A gradient estimator via L1-randomization for online zero-order
optimization with two point feedback [93.57603470949266]
2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。
ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。
我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-05-27T11:23:57Z) - A Convergent and Dimension-Independent Min-Max Optimization Algorithm [32.492526162436405]
min-playerがパラメータを更新するために使用する分布は、滑らかで非凹凸関数に依存していることを示す。
我々のアルゴリズムは、繰り返しに依存しない多くの反復において近似的な局所平衡に収束する。
論文 参考訳（メタデータ） (2020-06-22T16:11:30Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。
本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。
ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文 参考訳（メタデータ） (2020-06-11T19:40:38Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - A New Randomized Primal-Dual Algorithm for Convex Optimization with
Optimal Last Iterate Rates [16.54912614895861]
我々は,非滑らかな制約付き凸最適化問題のクラスを解くために,新しいランダム化ブロック座標原始双対アルゴリズムを開発した。
我々は,一般凸性と強い凸性という2つのケースにおいて,アルゴリズムが最適収束率を達成することを証明した。
その結果,提案手法は異なる実験における性能向上に寄与していることがわかった。
論文 参考訳（メタデータ） (2020-03-03T03:59:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。