High-Order Error Bounds for Markovian LSA with Richardson-Romberg Extrapolation
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation
We address the problem of solving strongly convex and smooth minimization problems using stochastic gradient descent (SGD) algorithm with a constant step size. Previous works suggested to combine the Polyak-Ruppert avera…
Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes
We consider Linear Stochastic Approximation (LSA) with a constant stepsize and Markovian data. Viewing the joint process of the data and LSA iterate as a time-homogeneous Markov chain, we prove its convergence to a uniqu…
Computing the Bias of Constant-step Stochastic Approximation with Markovian Noise
We study stochastic approximation algorithms with Markovian noise and constant step-size $\alpha$. We develop a method based on infinitesimal generator comparisons to study the bias of the algorithm, which is the expecte…
Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
We consider the dynamics of a linear stochastic approximation algorithm driven by Markovian noise, and derive finite-time bounds on the moments of the error, i.e., deviation of the output of the algorithm from the equili…
Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity
This paper deals with stochastic optimization problems involving Markovian noise with a zero-order oracle. We present and analyze a novel derivative-free method for solving such problems in strongly convex smooth and non…
Stochastic Optimization