BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/112
DTSTAMP:20230914T125910Z
SUMMARY:On Stability and Sample Complexity of Stochastic Approximation Iter
ates
DESCRIPTION:Speaker: Sameer Kamal\nSchool of Technology and Computer Scienc
e\nTata Institute of Fundamental Research\nHomi Bhabha Road\n\nAbstract: \
n(i) We propose and analyze a new scheme for stabilizing the stochastic ap
proximation iterates\, viz.\, an adaptation of step sizes that controls th
e growth of the iterates without affecting their asymptotic behavior. This
amounts to scaling the step sizes appropriately when the iterates are suf
ficiently far away from the origin. Only a finite random number of steps d
iffer from the original scheme\, and unlike the projection method\, this s
cheme does not introduce spurious equilibria. Further\, instead of requiri
ng the o.d.e. to descend the Lyapunov function everywhere where the functi
on isn't at its minimum\, we only require it to do so outside a sphere of
arbitrarily large radius. [http://arxiv.org/abs/1007.4689]\n\n(ii) Sample
complexity refers to the number of samples needed to be within a specific
distance from the attracting set of the o.d.e. with a given probability p
rovided that the iterates enter its domain of attraction with the step siz
e sufficiently small at the time of entry. In previous work by Borkar\, sa
mple complexity estimates were obtained under the assumption that the suit
ably re-scaled martingale difference noise remains bounded. We recover the
se results under a much weaker condition that only requires the re-scaled
martingale differences to have an exponentially decaying conditional tail
probability. [http://arxiv.org/abs/1007.4684]\n
URL:https://www.tcs.tifr.res.in/web/events/112
DTSTART;VALUE=DATE:20100831
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR