Stochastic approximation with set-valued maps and Markov noise: Theoretical foundations and applications

Abstract

Stochastic approximation algorithms produce estimates of a desired solution using noisy real world data. Introduced by Robbins and Monro, in 1951, stochastic approximation techniques have been instrumental in the asymptotic analysis of several adaptive algorithms in learning, signal processing and control. A popular method for the analysis of stochastic approximation schemes is the dynamical systems approach or the o.d.e. method introduced by Ljung and developed further extensively by Benaim and Hirsch. We build upon the works of Benaim et.al. and Bhatnagar et.al., and present the asymptotic analysis of stochastic approximation schemes with set-valued drift functions and nonadditive Markov noise. The frame- works studied by us are under the weakest set of assumptions and encompass a majority of the methods studied to date. We first present the asymptotic analysis of stochastic approximation schemes with set-valued drift function and non-additive iterate-dependent Markov noise. We show that a linearly interpolated trajectory of such a recursion is an asymptotic pseudotrajectory for the flow of a limiting differential inclusion obtained by averaging the set-valued drift function of the recursion with respect to the stationary distributions of the Markov noise. The limit set theorem by Benaim is then used to characterize the limit sets of the recursion in terms of the dynamics of the limiting differential inclusion. The analysis presented allows us characterize the asymptotic behavior of controlled stochastic approximation, subgradient descent, approximate drift problem and analysis of discontinuous dynamics all in the presence of non-additive iterate-dependent Markov noise. Next we present the asymptotic analysis of a stochastic approximation scheme on two timescales with set- valued drift functions and in the presence of non-additive iterate-dependent Markov noise. It is shown that the recursion on each timescale tracks the flow of a differential inclusion obtained by averaging the set-valued drift function in the recursion with respect to a set of measures which take into account both the averaging with respect to the stationary distributions of the Markov noise terms and the interdependence between the two recursions on different timescales. Finally, we present the analysis of stochastic approximation schemes with set-valued maps in the absence of a stability guarantee. We prove that after a large number of iterations if the stochastic approximation process enters the domain of attraction of an attracting set it gets locked into the attracting set with high probability. We demonstrate that the above result is an effective instrument for analyzing stochastic approximation schemes in the absence of a stability guarantee, by using it to obtain an alternate criterion for convergence in the presence of a locally attracting set for the mean field and by using it to show that a feedback mechanism, which involves resetting the iterates at regular time intervals, stabilizes the scheme when the mean field possesses a globally attracting set, thereby guaranteeing convergence. Our results build on the works of Borkar, Andrieu et al. and Chen et al., by allowing for the presence of set-valued drift functions.