論文の概要: True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration

• arxiv url: http://arxiv.org/abs/2605.30532v1
• Date: Thu, 28 May 2026 20:09:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-01 20:56:50.211126
• Title: True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration
• Title（参考訳）: Markov-Chain Monte Carlo統合の高速化のための真の自己回避ウォーク
• Authors: Qinghua, Ding, Venkat Anantharam,
• Abstract要約: TSAWはマルコフ連鎖モンテカルロによる経験的積分推定を改善するメカニズムである。 有限集合上の既約マルコフ核$P$に付随する有限状態適応サンプリングダイナミクスを考える。 すべての有界関数 $f:Vtomathbb R$ に対して、積分推定子の誤差は [左|frac1tsum_s=0t-1 f(X_s)-sum_iin V_i f(i)right| = Oleft(fracsqrt) として収束する。
• 参考スコア（独自算出の注目度）: 9.734388236956597
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study true self-avoiding walk (TSAW) as a mechanism for improving empirical integral estimation via Markov chain Monte Carlo (MCMC). We consider finite-state adaptive sampling dynamics associated with an irreducible Markov kernel $P$ on a finite set, with stationary distribution $π$, in which the transition probabilities are penalized according to empirical overuse. Our main result is that the empirical occupation counts $L_t(i)$ and transition counts $N_t(i,j)$ of the resulting TSAW-based walk satisfy \[ L_t(i)-tπ_i = O(\sqrt{\log t}) \quad\text{and}\quad N_t(i,j)-tπ_iP_{ij}=O(\sqrt{\log t}) \qquad\text{almost surely} \] for every state $i$ and every edge $(i,j)$ with $P_{ij}>0$. Consequently, for every bounded function $f:V\to\mathbb R$, the error of our integral estimator converges as \[ \left|\frac1t\sum_{s=0}^{t-1} f(X_s)-\sum_{i\in V}π_i f(i)\right| = O\left(\frac{\sqrt{\log t}}{t}\right) \qquad\text{almost surely}. \] These results show that, in contrast with the usual $t^{-1/2}$ error scaling for empirical averages under standard random-walk-based methods, TSAW-based estimator yields empirical integral errors of order $O(\sqrt{\log t}/t)$ almost surely, thereby achieving a substantially sharper dependence on the sample size $t$.
• Abstract（参考訳）: マルコフ連鎖モンテカルロ(MCMC)による経験的積分推定を改善するメカニズムとして,真の自己回避歩行(TSAW)について検討した。 我々は、有限集合上の既約マルコフ核$P$に付随する有限状態適応サンプリング力学を、定常分布$π$とみなす。 我々の主な結果は、経験的占有が$L_t(i)$を数え、遷移が$N_t(i,j)$を数え、結果として得られるTSAWベースのウォークの満足度が \[L_t(i)-tπ_i = O(\sqrt{\log t}) \quad\text{and}\quad N_t(i,j)-tπ_iP_{ij}=O(\sqrt{\log t}) \qquad\text{almost surely} \] を満たすことである。 したがって、すべての有界函数 $f:V\to\mathbb R$ に対して、積分推定子の誤差は \[ \left|\frac1t\sum_{s=0}^{t-1} f(X_s)-\sum_{i\in V}π_i f(i)\right| = O\left(\frac {\sqrt{\log t}}{t}\right) \qquad\text{almost surely} として収束する。 以上の結果から, 標準ランダムウォーク法における経験的平均値に対する通常の$t^{-1/2}$エラースケーリングとは対照的に, TSAW を用いた推定器は次数 $O(\sqrt{\log t}/t)$ の経験的積分誤差をほぼ確実に生成し, サンプルサイズ $t$ に大きく依存することを示す。

関連論文リスト

• A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance [7.014801584517052]
  我々は,分散レベルと出力レベルの両方でエラーを定量化する,Top-$$ attention truncationという統一フレームワークを開発した。 総偏差距離は捨てられたソフトマックスのテール質量と一致し,$mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$を満たすことを示す。
  論文  参考訳（メタデータ） (2025-12-08T15:36:41Z)
• On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm [52.95596504632859]
  本稿では、$ell_1$ノルムで測定されたAdamWに対して、収束速度 $frac1Ksum_k=1KEleft[||nabla f(xk)||_1right]leq O(fracsqrtdCK1/4)$を確立する。 結果は、二重モーメント機構を用いたAdamW変種であるNAdamWに拡張し、同じ収束率を維持していることを示す。
  論文  参考訳（メタデータ） (2025-05-17T05:02:52Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• 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)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning [3.8098187557917464]
  この論文は$d$-dimensional recursion approximation, $$theta_n+1=theta_n + alpha_n + 1 f(theta_n, Phi_n+1)に関するものである。 主な結果は、ドスカー・バラダン・リャプノフドリフト条件(DV3)の平均流とバージョンに関する追加条件の下で確立される。 a example is given where $f$ and $barf$ are linear in $theta$, and $Phi$ is a geometryal.
  論文  参考訳（メタデータ） (2021-10-27T13:38:25Z)
• From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical Approximation and Statistical Applications [18.618590805279187]
  我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。 我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
  論文  参考訳（メタデータ） (2021-01-11T17:23:24Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。 最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
  論文  参考訳（メタデータ） (2020-11-24T22:39:21Z)
• Multivariate mean estimation with direction-dependent accuracy [8.147652597876862]
  独立な同一分布観測に基づくランダムベクトルの平均を推定する問題を考察する。 確率ベクトルの1次元辺の分散があまり小さくない全ての方向において、ほぼ最適誤差を持つ推定器を証明した。
  論文  参考訳（メタデータ） (2020-10-22T17:52:45Z)

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

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