On Stochastic Approximations Driven by Sample Averages: Convergence Results via the ODE Method

Simple item page
dc.contributor.authorBartusek, John D.en_US
dc.contributor.authorMakowski, Armand M.en_US
dc.contributor.departmentISRen_US
dc.contributor.departmentCSHCNen_US
dc.date.accessioned2007-05-23T09:58:11Z
dc.date.available2007-05-23T09:58:11Z
dc.date.issued1994en_US
dc.description.abstractWe consider a class of projected stochastic approximation algorithms drive by sample averages. These algorithms arise naturally in problems of on-line parametric optimization for discrete event dynamical systems., e.g., queueing systems and Petri net models. We develop a general framework for investigating the a.s. convergence of the iterate sequence, and show how such convergence results can be obtained by means of the ordinary differential equation (ODE) method under a condition of exponential convergence. We relate this condition of exponential convergence to certain Large Deviations upper bounds which are uniform in both the parameter q and the initial condition x. To demonstrate the applicability of the results, we specialize them to two specific classes of state processes, namely sequences of i.i.d. random variables and finite state time-homogeneous Markov chains. In both cases, we identify simple (and checkable) conditions that ensure the validity of a uniform Large Deviations upper bound.en_US
dc.format.extent2726598 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/5589
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1994-4en_US
dc.relation.ispartofseriesCSHCN; TR 1994-8en_US
dc.subjectqueueing networksen_US
dc.subjectadaptive controlen_US
dc.subjectoptimizationen_US
dc.subjectstochastic systemsen_US
dc.subjectCommunication en_US
dc.subjectSignal Processing Systemsen_US
dc.titleOn Stochastic Approximations Driven by Sample Averages: Convergence Results via the ODE Methoden_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_94-4.pdf
Size:
2.6 MB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports