論文の概要: 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} でなされた経験的な観察の一部を確認する。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - 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) - Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。
所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
論文 参考訳（メタデータ） (2024-05-23T11:46:03Z) - Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond $1+\alpha$ Moments [10.889739958035536]
本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。
平均値の中央値は近傍最適であり, 一定の要因が得られている。
定数係数のずれのない近傍分離推定器を見つけることは自由である。
論文 参考訳（メタデータ） (2023-11-21T18:50:38Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。