School of Technology and Computer Science Seminars

Improved Sample Complexity Estimates for Stochastic Approximation Algorithms

by Mr. Gugan Thoppe (School of Technology and Computer Science, TIFR)

Thursday, April 30, 2015 from to (Asia/Kolkata)
at D-405 (D-Block Seminar Room)
Description
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).