{"ID":2885347,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.05570","arxiv_id":"2508.05570","title":"High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation","abstract":"In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We focus on the version of the algorithm with constant step size $α$ and propose a novel decomposition of the bias via a linearization technique. We analyze the structure of the bias and show that the leading-order term is linear in $α$ and cannot be eliminated by PR averaging. To address this, we apply the Richardson-Romberg (RR) extrapolation procedure, which effectively cancels the leading bias term. We derive high-order moment bounds for the RR iterates and show that the leading error term aligns with the asymptotically optimal covariance matrix of the vanilla averaged LSA iterates.","short_abstract":"In this paper, we study the bias and high-order error bounds of the Linear Stochastic Approximation (LSA) algorithm with Polyak-Ruppert (PR) averaging under Markovian noise. We focus on the version of the algorithm with constant step size $α$ and propose a novel decomposition of the bias via a linearization technique....","url_abs":"https://arxiv.org/abs/2508.05570","url_pdf":"https://arxiv.org/pdf/2508.05570v1","authors":"[\"Ilya Levin\",\"Alexey Naumov\",\"Sergey Samsonov\"]","published":"2025-08-07T17:02:11Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\",\"math.OC\",\"math.ST\"]","methods":"[]","has_code":false}