Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting

The connection between diffusion processes and homogeneous Markov chains has been investigated for a long time Skorokhod [1963]. If we need to approximate the given diffusion by some homogeneous Markov chain, it is easy to realize because we are free to construct the chain nicely, meaning that we can choose terms and properties of MC, e.g., as it was shown in Raginsky et al. [2017]. However, often the inverse problem arises, namely, we have the a priori given chain, and the goal is to study it via the corresponding diffusion approximation. This task is an increasingly popular and hot research topic. Indeed, it is used to investigate different sampling techniques Orvieto and Lucchi [2018], to describe the behavior of optimization methods Raginsky et al. [2017] and to understand the convergence of boosting algorithms Ustimenko and Prokhorenkova [2021]. From practical experience, the given Markov chain may not have good properties that are easy to analyze in theory. Thus, the aim of our work is to study when diffusion approximation holds for as broad as the possible class of homogeneous Markov chains, i.e., we want to consider the maximally general chain and place the broadest possible assumptions on it whilst obtaining diffusion approximation guarantee.