論文の概要: Condition-number-independent Convergence Rate of Riemannian Hamiltonian
Monte Carlo with Numerical Integrators
- arxiv url: http://arxiv.org/abs/2210.07219v1
- Date: Thu, 13 Oct 2022 17:46:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-14 17:45:34.569539
- Title: Condition-number-independent Convergence Rate of Riemannian Hamiltonian
Monte Carlo with Numerical Integrators
- Title（参考訳）: 数値積分器を用いたリーマンハミルトニアンモンテカルロの条件数非依存収束速度
- Authors: Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh S. Vempala
- Abstract要約: 我々は、$m制約のあるポリトープ上の$e-alphatopx$の形式での分布に対して、一般的に使用される$の族の収束率は、$leftVert alpharightVert$とポリトープの幾何学とは独立であることを示す。
これらの保証は、多様体と積分子のパラメータの項で$e-f(x)$という形の密度の収束率の一般境界に基づいている。
- 参考スコア（独自算出の注目度）: 22.49731518828916
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the convergence rate of discretized Riemannian Hamiltonian Monte
Carlo on sampling from distributions in the form of $e^{-f(x)}$ on a convex set
$\mathcal{M}\subset\mathbb{R}^{n}$. We show that for distributions in the form
of $e^{-\alpha^{\top}x}$ on a polytope with $m$ constraints, the convergence
rate of a family of commonly-used integrators is independent of $\left\Vert
\alpha\right\Vert_2$ and the geometry of the polytope. In particular, the
Implicit Midpoint Method (IMM) and the generalized Leapfrog integrator (LM)
have a mixing time of $\widetilde{O}\left(mn^{3}\right)$ to achieve $\epsilon$
total variation distance to the target distribution. These guarantees are based
on a general bound on the convergence rate for densities of the form
$e^{-f(x)}$ in terms of parameters of the manifold and the integrator. Our
theoretical guarantee complements the empirical results of [KLSV22], which
shows that RHMC with IMM can sample ill-conditioned, non-smooth and constrained
distributions in very high dimension efficiently in practice.
- Abstract（参考訳）: 離散化されたリーマン・ハミルトニアン・モンテカルロの収束速度を、凸集合 $\mathcal{M}\subset\mathbb{R}^{n}$ 上の$e^{-f(x)}$ の形で分布からサンプリングする。
m$ 制約のあるポリトープ上の $e^{-\alpha^{\top}x}$ の形での分布に対しては、よく使われる積分器の族収束率は、$\left\vert \alpha\right\vert_2$ とポリトープの幾何とは独立である。
特に、暗黙的中点法(imm)と一般化されたleapfrog積分器(lm)は、目標分布に対する$\epsilon$の全変動距離を達成するために$\widetilde{o}\left(mn^{3}\right)$の混合時間を持つ。
これらの保証は、多様体と積分器のパラメータの観点で、$e^{-f(x)}$という形の密度の収束率の一般境界に基づいている。
我々の理論的保証は, [KLSV22] の実証結果を補完するもので, この結果から, RHMC と IMM を併用すれば, 極めて高次元の非平滑分布, 非平滑分布, 制約分布を効率的にサンプリングできることが示された。
関連論文リスト
- 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) - Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time? [8.74634652691576]
反復アルゴリズムのクラスで実現可能な分布のサブセット$mathscrF_m,alpha$について検討する。
統計物理学の非厳密な手法は、一般化されたパリの公式の言葉で$mathscrF_m,alpha$の間接的な特徴づけを与える。
論文 参考訳（メタデータ） (2024-06-05T05:54:56Z) - Further Understanding of a Local Gaussian Process Approximation: Characterising Convergence in the Finite Regime [1.3518297878940662]
非常に正確かつ大規模に拡張可能なGPnn回帰モデルに対するカーネル関数の一般的な選択は、データセットサイズ$n$の増加に伴って徐々に振る舞いに収束することを示す。
同様の境界はモデルの不特定の下で見出され、MSEと重要な校正計量の総合的な収束率を与えるために組み合わせられる。
論文 参考訳（メタデータ） (2024-04-09T10:47:01Z) - Efficient Estimation of the Central Mean Subspace via Smoothed Gradient
Outer Products [13.16054090477072]
マルチインデックスモデルに対する十分な次元削減の問題を考察する。
高速パラメトリック収束速度が$C_d cdot n-1/2$であることを示す。
論文 参考訳（メタデータ） (2023-12-24T12:28:07Z) - Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random
steps [0.0]
Hamiltonian Monte Carlo (HMC) は密度$e-f(x)$の高次元分布からサンプリングするマルコフ連鎖アルゴリズムである。
HMCは,$widetildeO(sqrtkappa d1/4 log(1/varepsilon)$グラデーションクエリを用いて,全変動距離で$varepsilon$-closeの分布からサンプリングできることを示す。
論文 参考訳（メタデータ） (2022-09-26T15:29:29Z) - 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) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - 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) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。