**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.