Name
Title | ||
|---|---|---|
On the Convergence, Lock-In Probability, and Sample Complexity of Stochastic Approximation |
Abstract | ||
|---|---|---|
It is shown that under standard hypotheses, if stochastic approximation iterates remain tight, they converge with probability one to what their o.d.e. limit suggests. A simple test for tightness (and therefore a.s. convergence) is provided. Further, estimates on lock-in probability, i.e., the probability of convergence to a specific attractor of the o.d.e. limit given that the iterates visit its domain of attraction, and sample complexity, i.e., the number of steps needed to be within a prescribed neighborhood of the desired limit set with a prescribed probability, are also provided. The latter improve significantly upon existing results in that they require a much weaker condition on the martingale difference noise. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1137/090769363 | SIAM J. Control and Optimization |
Keywords | Field | DocType |
simple test,sample complexity,standard hypothesis,specific attractor,stochastic approximation,lock-in probability,prescribed probability,tightness of iterates,weaker condition,stochastic approximation iterates,prescribed neighborhood,almost sure convergence,martingale difference noise,limit set | Convergence (routing),Attractor,Martingale difference sequence,Convergence of random variables,Mathematical optimization,Sample complexity,Iterated function,Stochastic approximation,Limit set,Mathematics | Journal |
Volume | Issue | ISSN |
48 | 8 | 0363-0129 |
Citations | PageRank | References |
3 | 0.70 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sameer Kamal | 1 | 4 | 1.07 |