論文の概要: On the Convergence of Langevin Monte Carlo: The Interplay between Tail
Growth and Smoothness
- arxiv url: http://arxiv.org/abs/2005.13097v1
- Date: Wed, 27 May 2020 00:26:20 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-28 08:32:15.788241
- Title: On the Convergence of Langevin Monte Carlo: The Interplay between Tail
Growth and Smoothness
- Title（参考訳）: ランゲヴィン・モンテカルロの収束について--タイル成長とスムースネスの相互作用
- Authors: Murat A. Erdogdu, Rasa Hosseinzadeh
- Abstract要約: リプシッツ勾配を持つポテンシャル、すなわち$beta=1$の場合、我々の速度は最もよく知られた依存性の速度を回復する。
この結果は、ターゲット分布において$nu_* = eff$、KL分割において$nu_*$に適用できる。
- 参考スコア（独自算出の注目度）: 10.482805367361818
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study sampling from a target distribution ${\nu_* = e^{-f}}$ using the
unadjusted Langevin Monte Carlo (LMC) algorithm. For any potential function $f$
whose tails behave like ${\|x\|^\alpha}$ for ${\alpha \in [1,2]}$, and has
$\beta$-H\"older continuous gradient, we prove that ${\widetilde{\mathcal{O}}
\Big(d^{\frac{1}{\beta}+\frac{1+\beta}{\beta}(\frac{2}{\alpha} -
\boldsymbol{1}_{\{\alpha \neq 1\}})} \epsilon^{-\frac{1}{\beta}}\Big)}$ steps
are sufficient to reach the $\epsilon $-neighborhood of a $d$-dimensional
target distribution $\nu_*$ in KL-divergence. This convergence rate, in terms
of $\epsilon$ dependency, is not directly influenced by the tail growth rate
$\alpha$ of the potential function as long as its growth is at least linear,
and it only relies on the order of smoothness $\beta$. One notable consequence
of this result is that for potentials with Lipschitz gradient, i.e. $\beta=1$,
our rate recovers the best known rate
${\widetilde{\mathcal{O}}(d\epsilon^{-1})}$ which was established for strongly
convex potentials in terms of $\epsilon$ dependency, but we show that the same
rate is achievable for a wider class of potentials that are degenerately convex
at infinity. The growth rate $\alpha$ starts to have an effect on the
established rate in high dimensions where $d$ is large; furthermore, it
recovers the best-known dimension dependency when the tail growth of the
potential is quadratic, i.e. ${\alpha = 2}$, in the current setup. Our
framework allows for finite perturbations, and any order of smoothness
${\beta\in(0,1]}$; consequently, our results are applicable to a wide class of
non-convex potentials that are weakly smooth and exhibit at least linear tail
growth.
- Abstract（参考訳）: 我々は,未調整のLangevin Monte Carlo (LMC)アルゴリズムを用いて,ターゲット分布の${\nu_* = e^{-f}}$からサンプリングする。
その尾が${\|x\|^\alpha}$ for ${\alpha \in [1,2]}$ であり、$\beta$-h\"older連続勾配を持つ任意のポテンシャル関数に対して、${\widetilde{\mathcal{o}} \big(d^{\frac{1}{\beta}+\frac{1+\beta}{\beta}(\frac{2}{\alpha}\boldsymbol{1}_{\{\alpha \neq 1\}})} \epsilon^{-\frac{1}{\beta}}\big)}$ステップは$\epsilon $-neighborhood of a $d$-dimensional target distribution $\nu_*$ in kl-divergence である。
この収束率は、$\epsilon$依存性という意味では、その成長が少なくとも線形である限り、ポテンシャル関数のテール成長率$\alpha$に直接影響されず、滑らかさの順序$\beta$のみに依存する。
この結果の顕著な結果の1つは、リプシッツ勾配を持つポテンシャル、すなわち$\beta=1$の場合、我々の速度は、$\epsilon$依存性の点で強い凸ポテンシャルに対して確立された最もよく知られた速度 ${\widetilde{\mathcal{O}}(d\epsilon^{-1})}$を回復するが、同じ速度は無限大の縮退したポテンシャルのより広いクラスに対して達成可能であることを示している。
成長率$\alpha$は、$d$が大きい高次元において確立された速度に影響を与え始め、さらに、ポテンシャルの尾成長が二次的であるときに最もよく知られた次元依存性、すなわち${\alpha = 2}$を現在の設定で回復する。
この枠組みは有限摂動と任意の平滑性の順序 ${\beta\in(0,1]}$ を許容するので、弱滑らかで少なくとも線形なテール成長を示す、幅広い非凸ポテンシャルのクラスに適用できる。
関連論文リスト
- On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - A qualitative difference between gradient flows of convex functions in
finite- and infinite-dimensional Hilbert spaces [2.7195102129095003]
凸対象関数に対する勾配流/勾配降下とボール/加速勾配降下の最適化について検討する。
ヒルベルト空間において、これは最適である:$f(x_t) - inf f$ は、モノトンが減少し$infty$で可積分である任意の関数と同じくらいゆっくりと$0$に崩壊することができる。
論文 参考訳（メタデータ） (2023-10-26T17:33:52Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳（メタデータ） (2023-09-29T14:14:53Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - High-dimensional Asymptotics of Feature Learning: How One Gradient Step
Improves the Representation [89.21686761957383]
2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。
我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
論文 参考訳（メタデータ） (2022-05-03T12:09:59Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Convergence Rate of the (1+1)-Evolution Strategy with Success-Based
Step-Size Adaptation on Convex Quadratic Functions [20.666734673282498]
1+1)-進化戦略(ES)と成功に基づくステップサイズ適応を一般凸二次関数で解析する。
1+1)-ES の収束速度は、一般凸二次函数上で明示的に厳密に導かれる。
論文 参考訳（メタデータ） (2021-03-02T09:03:44Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - 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) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。