論文の概要: Polynomial Mixing Times of Simulated Tempering for Mixture Targets by Conductance Decomposition
- arxiv url: http://arxiv.org/abs/2511.00708v1
- Date: Sat, 01 Nov 2025 21:16:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-05 16:37:26.904933
- Title: Polynomial Mixing Times of Simulated Tempering for Mixture Targets by Conductance Decomposition
- Title（参考訳）: 導電性分解による混合ターゲットの模擬温間加工の多項式混合時間
- Authors: Quan Zhou,
- Abstract要約: 位置シフトのみが異なる対数凹成分の混合物から採取した模擬温度計の理論的複雑さについて検討した。
主な結果は、メトロポリス・ランゲヴィンアルゴリズム(MALA)と組み合わせた模擬テンパリングの初めての保証を確立することである。
この証明は、拡張空間上に構築された補助マルコフ連鎖に適用される、$s$コンダクタンスの一般的な状態分解定理に基づいている。
- 参考スコア（独自算出の注目度）: 4.008356608627647
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the theoretical complexity of simulated tempering for sampling from mixtures of log-concave components differing only by location shifts. The main result establishes the first polynomial-time guarantee for simulated tempering combined with the Metropolis-adjusted Langevin algorithm (MALA) with respect to the problem dimension $d$, maximum mode displacement $D$, and logarithmic accuracy $\log \epsilon^{-1}$. The proof builds on a general state decomposition theorem for $s$-conductance, applied to an auxiliary Markov chain constructed on an augmented space. We also obtain an improved complexity estimate for simulated tempering combined with random-walk Metropolis. Our bounds assume an inverse-temperature ladder with smallest value $\beta_1 = O(D^{-2})$ and spacing $\beta_{i+1}/\beta_i = 1 + O( d^{-1/2} )$, both of which are shown to be asymptotically optimal up to logarithmic factors.
- Abstract（参考訳）: 位置シフトのみが異なる対数凹成分の混合物から採取した模擬温度計の理論的複雑さについて検討した。
主な結果は、模擬テンパリングの多項式時間保証とメトロポリス調整ランゲヴィンアルゴリズム(MALA)を併用した最初の多項式保証を、問題次元$d$、最大モード変位$D$、対数精度$\log \epsilon^{-1}$に対して確立する。
この証明は、拡張空間上に構築された補助マルコフ連鎖に適用される、$s$コンダクタンスの一般的な状態分解定理に基づいている。
また,ランダムウォークメトロポリスを併用した模擬テンパリングの複雑さ推定値も改善した。
我々の境界は、最小値 $\beta_1 = O(D^{-2})$ で、かつ $\beta_{i+1}/\beta_i = 1 + O(d^{-1/2} )$ を割った逆温度のはしごを仮定する。
関連論文リスト
- 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) - When does Metropolized Hamiltonian Monte Carlo provably outperform
Metropolis-adjusted Langevin algorithm? [4.657614491309671]
本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。
連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
論文 参考訳（メタデータ） (2023-04-10T17:35:57Z) - Faster high-accuracy log-concave sampling via algorithmic warm starts [6.117084972237769]
実際には、古典的なメトロポリス調整ランゲヴィンアルゴリズム(MALA)のような高精度なサンプリング器は事実上のゴールド標準のままである。
我々は,このサンプリング問題の次元依存性を$tildeO(d1/2)$に改善し,MALAでは$tildeO(d1/2)$とした。
我々の主な技術的貢献は、離散化アンダーダム化ランゲヴィン拡散に対する最初の$tildeO(d1/2)$ R'enyi混合速度を確立することでこの問題を解決することである。
論文 参考訳（メタデータ） (2023-02-20T19:27:21Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。
本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。
総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
論文 参考訳（メタデータ） (2021-02-09T02:44:24Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。