Abstract | ||
---|---|---|
Consider a contraction operator $T$ over a Banach space $mathcal X$ with a fixed point $x^star$. Assume that one can approximate the operator $T$ by a random operator $hat T^N$ using $Ninmathbb{N}$ independent and identically distributed samples of a random variable. Consider the sequence $(hat X^N_k)_{kinmathbb{N}}$, which is generated by $hat X^N_{k+1} = hat T^N(hat X^N_k)$ and is a random sequence. In this paper, we prove that under certain conditions on the random operator, (i) the distribution of $hat X^N_k$ converges to a unit mass over $x^star$ as $k$ and $N$ goes to infinity, and (ii) the probability that $hat X^N_k$ is far from $x^star$ as $k$ goes to infinity can be made arbitrarily small by an appropriate choice of $N$. We also find a lower bound on the probability that $hat X^N_k$ is far from $x^star$ as $krightarrow infty$. We apply the result to study probabilistic convergence of certain randomized optimization and value iteration algorithms. |
Year | Venue | Field |
---|---|---|
2018 | arXiv: Probability | Combinatorics,Random variable,Upper and lower bounds,Infinity,Banach space,Operator (computer programming),Independent and identically distributed random variables,Fixed point,Mathematics,Fixed-point theorem |
DocType | Volume | Citations |
Journal | abs/1804.01195 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Abhishek Gupta | 1 | 14 | 10.61 |
Rahul Jain | 2 | 784 | 71.51 |
Peter W. Glynn | 3 | 1527 | 293.76 |