Fugu-MT 論文翻訳(概要): Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo

論文の概要: 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次定常点を求める複雑性境界のサンプリングアナログであり、したがって非対数サンプリングの一般理論への第一歩となる。本研究では,ポインカル・ジャイの不等式を満たす分布からサンプリングする新たな最先端保証が得られることを示す。

関連論文リスト

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)
Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文参考訳（メタデータ） (2024-05-10T09:58:47Z)
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)
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence [3.9586758145580014]
強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。 $n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
論文参考訳（メタデータ） (2022-04-06T04:11:26Z)
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)
Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
推定値である$widetildemathcalO(depsilon-1)$が,これらの測定値の既知レートを改善することを示す。特に凸および1次滑らかなポテンシャルについて、LCCアルゴリズムは、これらの測定値の既知率を改善するために$widetildemathcalO(depsilon-1)$を推定する。
論文参考訳（メタデータ） (2020-07-22T18:18:28Z)
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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。