Title: Stochastic approximation - convergence and stability.
Speaker: Sameer Kamal, School of Technology and Computer Science, TIFR, Mumbai.
Time and Date: 4.00 pm, Wednesday February 9, 2011
Venue: Room 103 (ground floor), Mechanical Engineering
Abstract:
Stochastic approximation (SA) was originally introduced by Robbins and Monro as a scheme for finding zeros of a nonlinear function under noisy measurements. It has since become one of the main workhorses of statistical computation, signal processing, adaptive schemes in AI and economic models, etc. SA is an iterative procedure and typically one wants to characterize the asymptotic behaviour of the iterates. A common aim is to establish almost sure convergence of the iterates to a certain specific set. This usually involves two steps: (i) showing that the iterates are stable (i.e., bounded almost surely), and, (ii) assuming they are stable, showing that they converge to the desired set.
In the first part of this talk we discuss a vector minmax problem for controlled Markov chains. The solution illustrates techniques for proving convergence under stability. The problem of controlling afinite state Markov chain by an agent in the presence of an adversary so as to ensure desired performance levels for a vector of objectives is cast in the framework of Blackwell approachability. A control scheme is proposed which ensures almost sure convergence to the desired set regardless of the adversarial actions. A major ingredient in our convergence proof is a new and elementary `constructive' proof of two time scale structure. In the second part of the talk we present stability results which ensure that the iterates are bounded with probability one under fairly weak assumptions.
Speaker Bio: Sameer Kamal is a research scholar at the School of Technology and Computer Science, TIFR. He holds a M.Sc (integrated) in Physics from IIT Kanpur and a M.Sc (Engg) in Computer Science and Automation from IISc. He has worked in the software industry for several years. His areas of research are Applied Probability, Stochastic Approximation, and Random walks.