論文の概要: Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin
Algorithm
- arxiv url: http://arxiv.org/abs/2006.09270v2
- Date: Mon, 22 Feb 2021 15:12:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-20 20:11:06.411477
- Title: Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin
Algorithm
- Title（参考訳）: 近確率勾配Langevinアルゴリズムの2次主解釈
- Authors: Adil Salim and Peter Richt\'arik
- Abstract要約: ログ凹型確率分布に対するサンプリングの課題を考察する。
対象の分布は、ワッサーシュタイン空間上で定義されるクルバック・リーバーの発散の最小値と見なすことができる。
ポテンシャルが強い凸であれば、PSGLA の複雑さは 2-ワッサーシュタイン距離の点で$O (1/varepsilon2)$である。
- 参考スコア（独自算出の注目度）: 11.80267432402723
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the task of sampling with respect to a log concave probability
distribution. The potential of the target distribution is assumed to be
composite, \textit{i.e.}, written as the sum of a smooth convex term, and a
nonsmooth convex term possibly taking infinite values. The target distribution
can be seen as a minimizer of the Kullback-Leibler divergence defined on the
Wasserstein space (\textit{i.e.}, the space of probability measures). In the
first part of this paper, we establish a strong duality result for this
minimization problem. In the second part of this paper, we use the duality gap
arising from the first part to study the complexity of the Proximal Stochastic
Gradient Langevin Algorithm (PSGLA), which can be seen as a generalization of
the Projected Langevin Algorithm. Our approach relies on viewing PSGLA as a
primal dual algorithm and covers many cases where the target distribution is
not fully supported. In particular, we show that if the potential is strongly
convex, the complexity of PSGLA is $O(1/\varepsilon^2)$ in terms of the
2-Wasserstein distance. In contrast, the complexity of the Projected Langevin
Algorithm is $O(1/\varepsilon^{12})$ in terms of total variation when the
potential is convex.
- Abstract（参考訳）: 本稿では,ログ凹確率分布に対するサンプリングの課題について考察する。
対象分布のポテンシャルは、滑らかな凸項の和として書かれる合成値 \textit{i.e.} であり、非滑らかな凸項は無限の値を取ると仮定される。
対象分布は、wasserstein空間上で定義されるkullback-leiblerの発散の最小化と見なすことができる(\textit{i.e}、確率測度の空間)。
本論文の前半では、この最小化問題に対する強い双対性結果を確立する。
本論文の第2部では,第1部から発生する双対性ギャップを用いて,投影型ランジュバンアルゴリズムの一般化と見なすことができる近位確率勾配ランジュバンアルゴリズム(psgla)の複雑性について検討する。
提案手法はPSGLAを原始双対アルゴリズムとみなし、対象分布が完全にサポートされていない多くのケースをカバーする。
特に、ポテンシャルが強凸であれば、PSGLAの複雑さは2-ワッサーシュタイン距離の点で$O(1/\varepsilon^2)$である。
対照的に、射影ランゲヴィンアルゴリズムの複雑さは、ポテンシャルが凸であるときの総変分の観点からは$O(1/\varepsilon^{12})$である。
関連論文リスト
- 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) - 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) - Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
線形マルコフ決定過程(MDP)を学習するための新たな報酬なしアルゴリズムを提案する。
我々のアルゴリズムの核心は、探索駆動の擬似回帰を用いた不確実性重み付き値目標回帰である。
我々のアルゴリズムは$tilde O(d2varepsilon-2)$ episodesを探索するだけで、$varepsilon$-optimal policyを見つけることができる。
論文 参考訳（メタデータ） (2023-03-17T17:53:28Z) - Projected Stochastic Gradient Langevin Algorithms for Constrained
Sampling and Non-Convex Learning [0.0]
ランジュバンアルゴリズムは付加ノイズを持つ手法である。
ランジュバンアルゴリズムは何十年もチェーンカルロ(ミロン)で使われてきた
学習にとって、それはそれがそれが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それがそれが事実であるということであり、それがそれがそれが事実であるということであるということであるということが、それが事実であるということであるということが、それが事実であるということであることを示している。
論文 参考訳（メタデータ） (2020-12-22T16:19:20Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳（メタデータ） (2020-12-21T03:10:21Z) - Riemannian Langevin Algorithm for Solving Semidefinite Programs [9.340611077939828]
球面の積多様体上での非最適化とサンプリングのためのランゲヴィンに基づくアルゴリズムを提案する。
提案アルゴリズムは,高い確率で$epsilonの精度が得られることを示す。
論文 参考訳（メタデータ） (2020-10-21T17:51:08Z) - 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) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。