論文の概要: Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity
Guarantees for Langevin Monte Carlo
- arxiv url: http://arxiv.org/abs/2202.05214v1
- Date: Thu, 10 Feb 2022 18:20:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-11 17:59:47.920295
- Title: Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity
Guarantees for Langevin Monte Carlo
- Title(参考訳): 非対数サンプリングの理論に向けて:ランゲヴィン・モンテカルロの第一次定常保証
- Authors: Krishnakumar Balasubramanian, Sinho Chewi, Murat A. Erdogdu, Adil
Salim, Matthew Zhang
- Abstract要約: これは$mathdで$pi exp(-V)$を見つけるためのサンプリングイテレーションである。
多数の拡張応用について論じ、特に非凹凸サンプリングの一般理論への第一歩である。
- 参考スコア(独自算出の注目度): 24.00911089902082
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For the task of sampling from a density $\pi \propto \exp(-V)$ on
$\mathbb{R}^d$, where $V$ is possibly non-convex but $L$-gradient Lipschitz, we
prove that averaged Langevin Monte Carlo outputs a sample with
$\varepsilon$-relative Fisher information after $O( L^2 d^2/\varepsilon^2)$
iterations. This is the sampling analogue of complexity bounds for finding an
$\varepsilon$-approximate first-order stationary points in non-convex
optimization and therefore constitutes a first step towards the general theory
of non-log-concave sampling. We discuss numerous extensions and applications of
our result; in particular, it yields a new state-of-the-art guarantee for
sampling from distributions which satisfy a Poincar\'e inequality.
- Abstract(参考訳): 密度$\pi \propto \exp(-V)$ on $\mathbb{R}^d$, where $V$ is not-convex but $L$-gradient Lipschitz からサンプリングするタスクに対して、平均的なランジェヴィン・モンテ・カルロは、$O(L^2 d^2/\varepsilon^2)$反復の後、$\varepsilon$-relative Fisher情報を出力することを示した。
これは、非凸最適化における$\varepsilon$-approximate 1次定常点を求める複雑性境界のサンプリングアナログであり、したがって非対数サンプリングの一般理論への第一歩となる。
本研究では,ポインカル・ジャイの不等式を満たす分布からサンプリングする新たな最先端保証が得られることを示す。
関連論文リスト
- Diffusion at Absolute Zero: Langevin Sampling Using Successive Moreau Envelopes [52.69179872700035]
本稿では,$pi(x)proptoexp(-U(x))$という形のGibbs分布から,潜在的に$U(x)$でサンプリングする方法を提案する。
拡散モデルに着想を得て、ターゲット密度の近似の列 $(pit_k)_k$ を考えることを提案し、そこで$pit_kapprox pi$ for $k$ small に対して $pit_k$ は、$k$のサンプリングに好適な性質を示す。
論文 参考訳(メタデータ) (2025-02-03T13:50:57Z) - Polynomial time sampling from log-smooth distributions in fixed dimension under semi-log-concavity of the forward diffusion with application to strongly dissipative distributions [9.48556659249574]
固定次元の複雑なサンプリングアルゴリズムを提案する。
我々は,提案アルゴリズムが予測される$epsilon$誤差を$KL$ばらつきで達成することを証明する。
応用として、$L$-log-smooth分布からサンプリングする問題に対する指数関数的複雑性の改善を導出する。
論文 参考訳(メタデータ) (2024-12-31T17:51:39Z) - 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) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳(メタデータ) (2024-04-29T15:04:07Z) - Stochastic Langevin Monte Carlo for (weakly) log-concave posterior
distributions [0.0]
従来のランゲヴィン拡散にサンプリングステップを組み込んだ,[WT11] で導入されたランゲヴィンモンテカルロ法の連続時間バージョンについて検討する。
この方法は、後部分布をサンプリングする機械学習で人気がある。
論文 参考訳(メタデータ) (2023-01-08T17:08:21Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳(メタデータ) (2020-12-31T18:24:41Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳(メタデータ) (2020-10-19T15:23:18Z) - Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。
凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
論文 参考訳(メタデータ) (2020-10-07T01:43:07Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。