論文の概要: Optimal Scaling for the Proximal Langevin Algorithm in High Dimensions
- arxiv url: http://arxiv.org/abs/2204.10793v1
- Date: Thu, 21 Apr 2022 01:08:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-26 03:48:43.002589
- Title: Optimal Scaling for the Proximal Langevin Algorithm in High Dimensions
- Title(参考訳): 高次元における近位ランジュバンアルゴリズムの最適スケーリング
- Authors: Natesh S. Pillai
- Abstract要約: MALAは、ターゲット密度の対数勾配をその分布に組み込んだサンプリングアルゴリズムである。
本稿では, 2 倍の微分可能なターゲット密度の広いクラスにおいて, 近位MALAは高次元のMALAと同じ最適スケーリングを享受していることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Metropolis-adjusted Langevin (MALA) algorithm is a sampling algorithm
that incorporates the gradient of the logarithm of the target density in its
proposal distribution. In an earlier joint work \cite{pill:stu:12}, the author
had extended the seminal work of \cite{Robe:Rose:98} and showed that in
stationarity, MALA applied to an $N$-dimensional approximation of the target
will take ${\cal O}(N^{\frac13})$ steps to explore its target measure. It was
also shown in \cite{Robe:Rose:98,pill:stu:12} that, as a consequence of the
diffusion limit, the MALA algorithm is optimized at an average acceptance
probability of $0.574$. In \cite{pere:16}, Pereyra introduced the proximal MALA
algorithm where the gradient of the log target density is replaced by the
proximal function (mainly aimed at implementing MALA non-differentiable target
densities). In this paper, we show that for a wide class of twice
differentiable target densities, the proximal MALA enjoys the same optimal
scaling as that of MALA in high dimensions and also has an average optimal
acceptance probability of $0.574$. The results of this paper thus give the
following practically useful guideline: for smooth target densities where it is
expensive to compute the gradient while implementing MALA, users may replace
the gradient with the corresponding proximal function (that can be often
computed relatively cheaply via convex optimization) \emph{without} losing any
efficiency. This confirms some of the empirical observations made in
\cite{pere:16}.
- Abstract(参考訳): メトロポリス調整ランジュバン(metropolis-adjusted langevin、mala)アルゴリズムは、対象密度の対数勾配をその提案分布に組み込んだサンプリングアルゴリズムである。
初期の共同研究である \cite{pill:stu:12} において、著者は \cite{Robe:Rose:98} の楽譜を拡張し、定常性において、ターゲットの$N$次元近似にMALAを適用するには、目標測度を探索するために${\cal O}(N^{\frac13})$ステップが必要であることを示した。
また、拡散限界の結果として、MALAアルゴリズムは0.574$の平均受容確率で最適化される、と \cite{Robe:Rose:98,pill:stu:12} で示された。
\cite{pere:16} において、ペレイラは、ログターゲット密度の勾配を近位関数(主にMALA非微分可能なターゲット密度を実装することを目的とした)に置き換える、近位MALAアルゴリズムを導入した。
本稿では, 2 倍の微分可能なターゲット密度の広いクラスにおいて, 近位MALAはMALAと高次元で同じ最適なスケーリングをしており, 平均 0.574$ の許容確率を持つことを示す。
そこで本論文は,MALAを実装しながら勾配を計算するのに費用がかかるスムーズなターゲット密度に対して,ユーザは勾配を対応する近位関数に置き換える(凸最適化により比較的安価に計算できる)。
これは \cite{pere:16} でなされた経験的な観察の一部を確認する。
関連論文リスト
- Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳(メタデータ) (2023-11-21T18:50:38Z) - Unbiased Kinetic Langevin Monte Carlo with Inexact Gradients [0.9558392439655016]
動力学的ランゲヴィンダイナミクスに基づく後進手段の非バイアス化手法を提案する。
提案した推定器は偏りがなく、有限分散となり、中心極限定理を満たす。
実験により, 有効試料当たりの勾配評価の数は, 不正確な勾配を用いた場合においても, 寸法に依存しないことが示唆された。
論文 参考訳(メタデータ) (2023-11-08T21:19:52Z) - Accelerated Bayesian imaging by relaxed proximal-point Langevin sampling [4.848683707039751]
本稿では, 画像逆問題におけるベイズ推定を行うために, マルコフ近位連鎖モンテカルロ法を提案する。
モロー・ヨシダの滑らか化によって滑らかにあるいは正規化されるモデルに対しては、中間点は過度に損傷されたランゲヴィン拡散の暗黙の離散化と等価である。
kappa$-strongly log-concaveのターゲットに対しては、提供された非漸近収束解析も最適な時間ステップを特定する。
論文 参考訳(メタデータ) (2023-08-18T10:55:49Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Optimal Scaling for Locally Balanced Proposals in Discrete Spaces [65.14092237705476]
離散空間におけるMetropolis-Hastings (M-H) アルゴリズムの効率は、対象分布に依存しない受容率によって特徴づけられることを示す。
最適受容率の知識は、連続空間におけるステップサイズ制御と直接的に類似して、離散空間における提案分布の近傍サイズを自動的に調整することを可能にする。
論文 参考訳(メタデータ) (2022-09-16T22:09:53Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳(メタデータ) (2021-09-08T18:00:05Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文 参考訳(メタデータ) (2021-02-25T15:50:19Z) - Optimal dimension dependence of the Metropolis-Adjusted Langevin
Algorithm [22.19906823739798]
ログスムースと強くログ凹分布のクラス上のMALAの混合時間は$O(d)$です。
メトロポリタン調整の投影特性に基づく新しい技術は、ランゲビンSDEのよく研究された離散分析にMALAの研究を減少させる。
論文 参考訳(メタデータ) (2020-12-23T17:14:06Z) - Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse
Gradients and Adaptive Sampling [29.600975900977343]
我々はZOROと呼ばれる新しい$textbfZ$eroth-$textbfO$rder $textbfR$egularized $textbfO$ptimization法を提案する。
基礎となる勾配がイテレートでほぼスパースである場合、ZOROは目的関数を減少させる新しいイテレートを得るために、非常に少数の客観的関数評価を必要とする。
論文 参考訳(メタデータ) (2020-03-29T11:01:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。