Date & Time: Thursday, October 1, 2015, 16:00-17:00
Venue: Ramanujan Hall
Title: A concentration bound for stochastic approximation via Alekseev's formula
Speaker: Gugan Thoppe, School of Technology and Computer Science, TIFR Mumbai
Abstract: Stochastic approximation (SA) refers to algorithms that attempt to find optimal points or zeroes of a function when only its noisy estimates are available. Because of noise, the iterates of these algorithms often get pushed in unfavourable directions. Hence a crucial performance measure of an SA algorithm is the probability that after the lapse of a certain amount of time starting from $n_0,$ its iterates are within an $\epsilon-$ball of a desired solution, given that the $n_0-$th iterate was in some bigger neighbourhood of this solution. In this talk, we shall obtain a lower bound on this probability. For this, we shall use the Alekseev's analogue of the variation of constants formula for nonlinear systems and a concentration inequality for martingales, which we will prove separately (if time permits). As we shall see, the hypotheses under which this bound holds is significantly weaker as compared to available results in similar vein. This is joint work with Vivek S. Borkar.