A probability approximation framework: Markov process approach (Q6104007)

Let \((X_t)_{t \geq 0}\) and \((Y_k)_{k=0,1,2,\dots}\) be a continuous time and a discrete time homogeneous Markov processes, respectively in the same Polish space. The article gives a framework of comparing the distributions of \((X_t)_{t \geq 0}\) and \((Y_k)_{k=0,1,2,\dots}\), if the process \((Y_k)_{k=0,1,2,\dots}\) is considered as a discrete time approximation of \((X_t)_{t \geq 0}\). The approach extends the classical Lindeberg principle to the general Markov process setting, using Itô's formula of Markov process and Markov operator, and gives an upper bound on the difference of probability distributions of \(X_N\) and \(Y_N\) in the Wasserstein-1 distance. This framework is applied to three problems. (1) Approximating online the stochastic gradient descent \(w_k=w_{k-1}-\eta \nabla \psi(w_{k-1}, \zeta_k)\), which is used to minimize the mathematical expectation \(\mathbf{E}_\zeta \psi(w, \zeta)\). The approximation is performed by a stochastic differential equation (SDE) and ensures the error bound in the Wasserstein-1 distance of the order of \(|\ln(\eta)| \eta\). (2) Bounding the error between a SDE with \(\alpha\)-stable noise and its Euler-Maruyama discretization (\(\alpha \in (1,2)\)). In this case, the error bound has the order of \(\eta^{(2-\alpha)/\alpha}\), where \(\eta\) is the step size of discretization. (3) Approximating the \(d\)-dimensional standard normal distribution by the \(d\)-dimensional Brownian motion. In this case, the error bound has the order of \(n^{-1/2}\) if discretization is done on a unit horizon \(t \in[0,1]\) with a step \(1/n\).