論文の概要: Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar\'e Inequality

• arxiv url: http://arxiv.org/abs/2303.03589v1
• Date: Tue, 7 Mar 2023 01:45:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-08 16:55:19.960076
• Title: Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar\'e Inequality
• Title（参考訳）: Langevin Monte Carloの完全な分析に向けて: Poincar\'eの不平等を超えて
• Authors: Alireza Mousavi-Hosseini and Tyler Farghly and Ye He and Krishnakumar Balasubramanian and Murat A. Erdogdu
• Abstract要約: この研究プログラムはVemapalaとWibisonoによって始められ、彼はログソボレフの不等式で結果を確立した。 この結果は,初期化器がLangevin Monte Carlo (LMC) アルゴリズムの性能に与える影響を明示的に定量化する。
• 参考スコア（独自算出の注目度）: 15.941909642134085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Langevin diffusions are rapidly convergent under appropriate functional inequality assumptions. Hence, it is natural to expect that with additional smoothness conditions to handle the discretization errors, their discretizations like the Langevin Monte Carlo (LMC) converge in a similar fashion. This research program was initiated by Vemapala and Wibisono (2019), who established results under log-Sobolev inequalities. Chewi et al. (2022) extended the results to handle the case of Poincar\'e inequalities. In this paper, we go beyond Poincar\'e inequalities, and push this research program to its limit. We do so by establishing upper and lower bounds for Langevin diffusions and LMC under weak Poincar\'e inequalities that are satisfied by a large class of densities including polynomially-decaying heavy-tailed densities (i.e., Cauchy-type). Our results explicitly quantify the effect of the initializer on the performance of the LMC algorithm. In particular, we show that as the tail goes from sub-Gaussian, to sub-exponential, and finally to Cauchy-like, the dependency on the initial error goes from being logarithmic, to polynomial, and then finally to being exponential. This three-step phase transition is in particular unavoidable as demonstrated by our lower bounds, clearly defining the boundaries of LMC.
• Abstract（参考訳）: ランゲヴィン拡散は適切な機能的不等式仮定の下で急速に収束する。 したがって、離散化誤差を扱うための追加の滑らかさ条件により、ランジュバン・モンテカルロ(lmc)のような離散化も同様に収束することが期待できる。 この研究プログラムはVemapala and Wibisono (2019)によって始められ、ログソボレフの不等式で結果を確立した。 Chewi et al. (2022) は結果を Poincar\'e の不等式を扱うように拡張した。 本稿では,poincar\'eの不等式を超えて,この研究プログラムを限界まで押し上げる。 我々は、多項式分解重尾密度(すなわちコーシー型)を含む大きな密度のクラスで満たされる弱いポアンカーの不等式の下でランゲヴィン拡散と LMC の上下境界を確立する。 本結果は,初期化器がLCCアルゴリズムの性能に与える影響を明示的に定量化する。 特に、尾が準ガウスから亜指数へ、そして最後にコーシー様へと進むと、初期誤差への依存は対数的から多項式へ、そして最後に指数的であることを示す。 この3段階の位相遷移は、以下に示すように特に避けられないものであり、LCCの境界を明確に定義している。

関連論文リスト

• Error bounds for particle gradient descent, and extensions of the log-Sobolev and Talagrand inequalities [1.3124513975412255]
  対数ソボレフとポリャク-ロジャシエヴィチの不等式の両方を一般化した条件を満たすモデルに対して、流れは指数関数的に自由エネルギーの最小値の集合に収束することを示す。 また、Bakry-'Emery Theorem を一般化し、LSI/PLI の一般化が強い凹凸対を持つモデルに対して成り立つことを示す。
  論文  参考訳（メタデータ） (2024-03-04T12:57:26Z)
• Taming under isoperimetry [0.0]
  本稿では,ログの増大に伴う分布のサンプル化を目的としたLangevinベースのスキームであるmathbfsTULA$を提案する。 非漸近KLを導出し、結果としてLog-Sobolevの不等式を満たす。
  論文  参考訳（メタデータ） (2023-11-15T14:44:16Z)
• When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm? [4.657614491309671]
  本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。 連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
  論文  参考訳（メタデータ） (2023-04-10T17:35:57Z)
• Non-asymptotic analysis of Langevin-type Monte Carlo algorithms [0.0]
  連続性の有限モジュラーを持つギブス分布からサンプリングするランゲヴィン型アルゴリズムについて、必ずしも0に収束しない。 ランゲヴィン・モンテカルロアルゴリズムは、ポテンシャルが散逸し、勾配が一様連続である場合、ギブス分布を任意の精度で近似できることを示す。
  論文  参考訳（メタデータ） (2023-03-22T09:16:17Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Lassoed Tree Boosting [53.56229983630983]
  有界断面変動のカドラー関数の大きな非パラメトリック空間において,早期に停止するn-1/4$ L2の収束速度を持つ勾配向上木アルゴリズムを証明した。 我々の収束証明は、ネストしたドンスカー類の経験的損失最小化子による早期停止に関する新しい一般定理に基づいている。
  論文  参考訳（メタデータ） (2022-05-22T00:34:41Z)
• Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev [25.18241929887685]
  離散時間ランゲヴィンモンテカルロアルゴリズムに対する最初の収束保証を提供する。 従来の研究とは異なり、我々の結果は滑らかさの弱さを許容し、凸性や解離性条件を必要としない。
  論文  参考訳（メタデータ） (2021-12-23T15:56:33Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
  我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。 平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。 任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-06-16T20:53:04Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。