True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration

• URL: http://arxiv.org/abs/2605.30532v1
• Date: Thu, 28 May 2026 20:09:36 GMT
• Title: True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration
• Abstract summary: TSAW is a mechanism for improving empirical integral estimation via Markov chain Monte Carlo.<n>We consider finite-state adaptive sampling dynamics associated with an irreducible Markov kernel $P$ on a finite set.<n>For every bounded function $f:Vtomathbb R$, the error of our integral estimator converges as [ left|frac1tsum_s=0t-1 f(X_s)-sum_iin V_i f(i)right| = Oleft(fracsqrt
• Score: 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$.

Related papers

• Simultaneous Pointwise Majorization for Mixed Tail Processes with Applications in Gaussian Chaos and Ergodic Diffusions [15.386375612838371]
  Classical chaining controls an indexed process through a single worst-case bound.<n>We develop the first simultaneous pointwise majorization theory for Banach-valued processes.
  arXiv  Detail & Related papers  (2026-09-01T17:42:38Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance [7.014801584517052]
  We develop a unified framework certified Top-$k$ attention truncation that quantifies error at both the distribution and output levels.<n>We show that the total-variation distance coincides with the discarded softmax tail mass and satisfies $mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$.
  arXiv  Detail & Related papers  (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]
  This paper establishes the convergence rate $frac1Ksum_k=1KEleft[||nabla f(xk)||_1right]leq O(fracsqrtdCK1/4)$ for AdamW measured by $ell_1$ norm.<n>We extend our result to NAdamW, an AdamW variant that employs a double-momentum mechanism, and demonstrate that it maintains the same convergence rate.
  arXiv  Detail & Related papers  (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]
  This paper considers the RMSProp and its momentum extension and establishes the convergence rate of $frac1Tsum_k=1T.<n>Our convergence rate matches the lower bound with respect to all the coefficients except the dimension $d$.<n>Our convergence rate can be considered to be analogous to the $frac1Tsum_k=1T.
  arXiv  Detail & Related papers  (2024-02-01T07:21:32Z)
• Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
  We show that a dataset of size $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. Our findings give rise to a unified approach to statistical inference of a wide class of statistical functionals of $etapi$.
  arXiv  Detail & Related papers  (2023-09-29T14:14:53Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning [3.8098187557917464]
  The paper concerns the $d$-dimensional recursion approximation, $$theta_n+1= theta_n + alpha_n + 1 f(theta_n, Phi_n+1) The main results are established under additional conditions on the mean flow and a version of the Donsker-Varadhan Lyapunov drift condition known as (DV3) An example is given where $f$ and $barf$ are linear in $theta$, and $Phi$ is a geometrical
  arXiv  Detail & Related papers  (2021-10-27T13:38:25Z)
• From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical Approximation and Statistical Applications [18.618590805279187]
  We show that $mathsfW_p(sigma)$ is controlled by a $pth order smooth dual Sobolev $mathsfd_p(sigma)$. We derive the limit distribution of $sqrtnmathsfd_p(sigma)(hatmu_n,mu)$ in all dimensions $d$, when $mu$ is sub-Gaussian.
  arXiv  Detail & Related papers  (2021-01-11T17:23:24Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. We design an estimator which attains the smallest possible confidence interval as a function of $n,d,delta$.
  arXiv  Detail & Related papers  (2020-11-24T22:39:21Z)
• Multivariate mean estimation with direction-dependent accuracy [8.147652597876862]
  We consider the problem of estimating the mean of a random vector based on $N$ independent, identically distributed observations. We prove an estimator that has a near-optimal error in all directions in which the variance of the one dimensional marginal of the random vector is not too small.
  arXiv  Detail & Related papers  (2020-10-22T17:52:45Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.