|dc.contributor.author||Yaji, Vinayaka Ganapati||
|dc.description.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
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.||en_US
|dc.rights||I grant Indian Institute of Science the right to archive and to make available my thesis or dissertation in whole or in part in all forms of media, now hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part
of this thesis or dissertation||en_US
|dc.subject||Stochastic approximation algorithms||en_US
|dc.subject||nonadditive Markov noise||en_US
|dc.subject.classification||Research Subject Categories::TECHNOLOGY::Information technology::Computer science||en_US
|dc.title||Stochastic approximation with set-valued maps and Markov noise: Theoretical foundations and applications||en_US
|dc.degree.grantor||Indian Institute of Science||en_US