Tata Institute of Fundamental Research

Improved Sample Complexity Estimates for Stochastic Approximation Algorithms

STCS Student Seminar
Speaker: Gugan Thoppe
Organiser: Tulasi mohan Molli
Date: Thursday, 30 Apr 2015, 14:00 to 15:30
Venue: D-405 (D-Block Seminar Room)

(Scan to add to calendar)
Abstract:  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).