Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
This provides theoretical foundations for analyzing convergence in data-driven applications like optimization and Markov decision processes, but it is incremental as it extends existing frameworks.
The paper tackles the problem of establishing limit properties for Markov chains induced by stochastic recursive algorithms, such as stochastic gradient descent, by showing that the distribution of sequences from iterated random operators converges weakly to trajectories of contraction operators and that time averages converge to spatial means under certain conditions.
Recursive stochastic algorithms have gained significant attention in the recent past due to data driven applications. Examples include stochastic gradient descent for solving large-scale optimization problems and empirical dynamic programming algorithms for solving Markov decision problems. These recursive stochastic algorithms approximate certain contraction operators and can be viewed within the framework of iterated random operators. Accordingly, we consider iterated random operators over a Polish space that simulate iterated contraction operator over that Polish space. Assume that the iterated random operators are indexed by certain batch sizes such that as batch sizes grow to infinity, each realization of the random operator converges (in some sense) to the contraction operator it is simulating. We show that starting from the same initial condition, the distribution of the random sequence generated by the iterated random operators converges weakly to the trajectory generated by the contraction operator. We further show that under certain conditions, the time average of the random sequence converges to the spatial mean of the invariant distribution. We then apply these results to logistic regression, empirical value iteration, and empirical Q value iteration for finite state finite action MDPs to illustrate the general theory develop here.