Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 37 min ago
PreprintarXiv licencearXiv

Berry--Esseen bounds for stochastic approximation with Markovian noise

  • Zhijun Cai
  • YUjie Qin
  • Zhuosong Zhang
Open at sourcePDFDOICite

Abstract

This paper studies the convergence rate of the Polyak-Ruppert average estimator in one-dimensional linear stochastic approximation recursion driven by Markov chains, allowing the Markov chain to start from any initial distribution. Under the conditions of positive Harris recurrence, non-periodicity, and one-step domination, combined with the fourth-moment condition of the coefficient function with respect to the stationary distribution, this paper uses the exchangeable pair technique to prove that after deterministic bias correction for the average estimator, a Berry--Esseen bound of order n−α/2 can be obtained, where the step size exponent is α∈ (1/2, 1). Moreover, for the statistics without bias correction and after variance normalization, the asymptotic normal approximation error is asymptotically equivalent to a normal constant multiplied by n1/2 − α.

Related

  1. Berry--Esseen Bounds for High-Temperature Ising Models
    Timothy M. Garoni, Aram Perez
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv
  2. Berry--Esseen Bounds for Faces in Unimodular Triangulations of Random Polytopes
    Zhonggen Su, Huilian Zheng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  3. Berry-Esseen bounds for products of random matrices under a 2+δ polynomial moment
    Zhi-Jun Cai, Qi-Man Shao, Hui Xiao +1
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  4. Improved Berry-Esseen bounds for multivariate nonlinear statistics in convex distance
    Zhi-Jun Cai, Jing-Cai Yang, Zhuo-Song Zhang
    arXivPreprintarXiv licenceFull textProbabilityStatisticsarXiv
  5. Berry-Esseen Bounds for the Number of Real Zeros of Gaussian Weyl Polynomials
    Yuchen Wang, Dawei Lu, Song-Hao Liu
    arXivPreprintarXiv licenceFull textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{cai2026berryesseen,
  title = {{Berry--Esseen bounds for stochastic approximation with Markovian noise}},
  author = {Zhijun Cai and YUjie Qin and Zhuosong Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.35538},
  eprint = {2610.35538},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.35538},
}
RIS
TY  - UNPB
TI  - Berry--Esseen bounds for stochastic approximation with Markovian noise
AU  - Zhijun Cai
AU  - YUjie Qin
AU  - Zhuosong Zhang
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2610.35538
UR  - https://arxiv.org/abs/2610.35538
AB  - This paper studies the convergence rate of the Polyak-Ruppert average estimator in one-dimensional linear stochastic approximation recursion driven by Markov chains, allowing the Markov chain to start from any initial distribution. Under the conditions of positive Harris recurrence, non-periodicity, and one-step domination, combined with the fourth-moment condition of the coefficient function with respect to the stationary distribution, this paper uses the exchangeable pair technique to prove that after deterministic bias correction for the average estimator, a Berry--Esseen bound of order n^−α/2 can be obtained, where the step size exponent is α∈ (1/2, 1). Moreover, for the statistics without bias correction and after variance normalization, the asymptotic normal approximation error is asymptotically equivalent to a normal constant multiplied by n^1/2 − α.
ER  -