論文の概要: Faster high-accuracy log-concave sampling via algorithmic warm starts
- arxiv url: http://arxiv.org/abs/2302.10249v1
- Date: Mon, 20 Feb 2023 19:27:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-22 17:18:52.606356
- Title: Faster high-accuracy log-concave sampling via algorithmic warm starts
- Title（参考訳）: アルゴリズムウォームスタートによる高速高精度ログコンケーブサンプリング
- Authors: Jason M. Altschuler and Sinho Chewi
- Abstract要約: 実際には、古典的なメトロポリス調整ランゲヴィンアルゴリズム(MALA)のような高精度なサンプリング器は事実上のゴールド標準のままである。
我々は,このサンプリング問題の次元依存性を$tildeO(d1/2)$に改善し,MALAでは$tildeO(d1/2)$とした。
我々の主な技術的貢献は、離散化アンダーダム化ランゲヴィン拡散に対する最初の$tildeO(d1/2)$ R'enyi混合速度を確立することでこの問題を解決することである。
- 参考スコア（独自算出の注目度）: 6.117084972237769
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Understanding the complexity of sampling from a strongly log-concave and
log-smooth distribution $\pi$ on $\mathbb{R}^d$ to high accuracy is a
fundamental problem, both from a practical and theoretical standpoint. In
practice, high-accuracy samplers such as the classical Metropolis-adjusted
Langevin algorithm (MALA) remain the de facto gold standard; and in theory, via
the proximal sampler reduction, it is understood that such samplers are key for
sampling even beyond log-concavity (in particular, for distributions satisfying
isoperimetric assumptions).
In this work, we improve the dimension dependence of this sampling problem to
$\tilde{O}(d^{1/2})$, whereas the previous best result for MALA was
$\tilde{O}(d)$. This closes the long line of work on the complexity of MALA,
and moreover leads to state-of-the-art guarantees for high-accuracy sampling
under strong log-concavity and beyond (thanks to the aforementioned reduction).
Our starting point is that the complexity of MALA improves to
$\tilde{O}(d^{1/2})$, but only under a warm start (an initialization with
constant R\'enyi divergence w.r.t. $\pi$). Previous algorithms took much longer
to find a warm start than to use it, and closing this gap has remained an
important open problem in the field. Our main technical contribution settles
this problem by establishing the first $\tilde{O}(d^{1/2})$ R\'enyi mixing
rates for the discretized underdamped Langevin diffusion. For this, we develop
new differential-privacy-inspired techniques based on R\'enyi divergences with
Orlicz--Wasserstein shifts, which allow us to sidestep longstanding challenges
for proving fast convergence of hypocoercive differential equations.
- Abstract（参考訳）: 強い対数凹と対数平滑分布から高精度へのサンプリングの複雑さを理解することは、実用的、理論的両面の観点からの根本的な問題である。
実際には、古典的なメトロポリス調整ランゲヴィンアルゴリズム (MALA) のような高精度なサンプリングは事実上のゴールド標準のままであり、理論上は、近位サンプリング器の還元により、このようなサンプリング器は対数共振性を超えたサンプリングの鍵となる(特に等長的な仮定を満たす分布に対して)。
本研究では、このサンプリング問題の次元依存性を$\tilde{O}(d^{1/2})$に改善する一方、MALAの以前の最良の結果は$\tilde{O}(d)$である。
これにより、MALAの複雑さに関する長い作業が終了し、さらに、強いログ凹凸とそれ以上の(前述の削減による)高精度サンプリングの最先端保証につながります。
我々の出発点は、MALAの複雑さは$\tilde{O}(d^{1/2})$に改善されるが、温かいスタート(定数 R\enyi divergence w.r.t.$\pi$ による初期化)の下でのみ改善されるということである。
それまでのアルゴリズムは、それを使うよりも温かいスタートを見つけるのにずっと時間がかかり、このギャップを埋めることは、この分野において重要なオープンな問題のままである。
我々の主要な技術的貢献は、離散弱減衰ランジュバン拡散に対する最初の$\tilde{o}(d^{1/2})$ r\'enyi混合率を確立することでこの問題を解決している。
そこで我々は,orlicz--wassersteinシフトを用いたr\'enyi divergencesに基づく微分プライバシーに着想を得た新しい手法を開発した。
関連論文リスト
- High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm [12.405427902037971]
本稿では,$mathbbRd$の適切な凸部分集合である対象分布から近似サンプリングを行う1次サンプリング法を提案する。
提案手法は,事前条件付きLangevinアルゴリズムの単一ステップで生成したマルコフ連鎖にメトロポリス・ハスティングスフィルタを適用した結果である。
論文 参考訳（メタデータ） (2024-12-24T23:21:23Z) - Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling [28.931489333515618]
簡単なアンニール型Langevin Monte Carloアルゴリズムに対して$widetildeOleft(fracdbeta2cal A2varepsilon6right)のオラクル複雑性を確立する。
例えば、$cal A$ は対象分布 $pi$ と容易にサンプリング可能な分布を補間する確率測度の曲線の作用を表す。
論文 参考訳（メタデータ） (2024-07-24T02:15:48Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Improved dimension dependence of a proximal algorithm for sampling [16.147290924171692]
そこで本研究では,すべての古典的設定において,より優れた複雑性境界を実現するサンプリングアルゴリズムを提案する。
提案アルゴリズムは,2021年に導入した近位サンプルを用いた。
強い対数対数分布の場合、この手法は温度開始を伴わずに$tildemathcalO(kappa d1/2)$の複雑さを持つ。
LSI を満たす分布に対して、我々は $tilde MathcalO(hat kappa d1/2)$ ここで $hat kappa$ は滑らかさと滑らかさの比である。
論文 参考訳（メタデータ） (2023-02-20T16:44:48Z) - Neural Inference of Gaussian Processes for Time Series Data of Quasars [72.79083473275742]
クエーサースペクトルを完全に記述できる新しいモデルを提案する。
また、$textitNeural Inference$というガウス的プロセスパラメータの推論の新しいメソッドも導入しています。
CDRWモデルとNeural Inferenceの組み合わせはベースラインのDRWとMLEを大きく上回っている。
論文 参考訳（メタデータ） (2022-11-17T13:01:26Z) - Resolving the Mixing Time of the Langevin Algorithm to its Stationary
Distribution for Log-Concave Sampling [34.66940399825547]
本稿では,Langevinアルゴリズムの定常分布に対する混合時間の特徴について述べる。
本稿では,差分プライバシー文献からサンプリング文献へのアプローチを紹介する。
論文 参考訳（メタデータ） (2022-10-16T05:11:16Z) - Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for
Log-Concave Sampling [2.9972063833424216]
対数平滑かつ強い対数凹分布からサンプリングするために,メトロポリス調整ランゲヴィンアルゴリズム(MALA)の混合時間について検討した。
温暖化開始時に最適なミニマックス混合時間を確立する。
論文 参考訳（メタデータ） (2021-09-27T14:02:27Z) - 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) - Towards Sample-Optimal Compressive Phase Retrieval with Sparse and
Generative Priors [59.33977545294148]
O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。
この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
論文 参考訳（メタデータ） (2021-06-29T12:49:54Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。