Improved Sample Complexity Estimates for Stochastic Approximation Algorithms



Thursday, 30 April 2015, 14:00 to 15:30


  • D-405 (D-Block Seminar Room)


Abstract: The Alexeev's perturbation theory gives a method to compare solutions of a perturbed ordinary differential equation (ODEs) with that of the unperturbed one. In this talk, we shall discuss an approach based on this method to obtain sample complexity estimates of stochastic approximation (SA) algorithms. Note that sample complexity refers to the probability that the SA iterates $x_{n}$ are within an $\epsilon-$neighbourhood of the equilibrium after lapse of a certain amount of time, conditioned on the event that $x_{n_0}$ was in some bigger neighbourhood of the equilibrium (this is a working paper with Prof. V. Borkar).