What is the stochastic analogue of convergence to the global minimizer when iterates are stochastic? Let $f: \mathbb{R}^n \to \mathbb{R}$ be a differentiable and strongly convex function with $m>0$ as follows:
$$
f(y) \geq f(x) + \nabla f(x)^T(y-x) + \frac{m}{2}||x-y||^2 \quad \forall x,y \in \mathbb{R}^n
$$
Also, let $(x_k)_{k\ge 0}$ be a given sequence such that the corresponding function value sequence is nonincreasing, i.e., $(f(x_k))_{k\ge 0}$.
Then, one can show $x_k\to x_*$ where $x_*$ is the unique global minimizer of $f(x)$. To show this we need to use the following assumptions:

*

*Nonincreasing sequence, i.e., $(f(x_k))_{k\ge 0}$

*$\nabla f(x_*)=0$
Question:
What is the stochastic analogue of the above case?
Is it $ \lim\limits_{k\to \infty}\text{Prob}\{ \|x_k- x_*\|> \epsilon \} =0 $ for a random sequence of $(x_k)_{k\ge 0}$.
If so, how one can prove this and what conditions he should impose to get this result.
I really appreciate if you can introduce some references that solves my problem.
 A: You will have to explain what stochastic version of the algorithm you consider for solving your problem. Right now, the problem you are stating in deterministic and there is no algorithm involved for solving the problem; i.e. finding the minimum of $f$.
In any way, since you can view an iterative algorithm as a discrete-time dynamical system, then one can define a stochastic version of the algorithm as a stochastic discrete-time dynamical system. Many concepts of convergence exist for such the solutions of such systems such as convergence in probability (which is the one you describe) almost sure convergence, convergence in distribution, and moment convergence such as in mean and mean-square.
Very often, convergence properties of discrete-time dynamical systems are shown by constructing Lyapunov functions which are decreasing, in a certain sense, along the trajectories of the algorithm/system.
Any resource on stochastic discrete-time system will be a good starting point such as the books by Söderström, "Discrete-time Stochastic Systems", van Schuppen, "Control and System Theory of Discrete-Time Stochastic Systems", and Dragan, Morozan, and Stoica, "Mathematical methods in robust control of discrete-time linear stochastic systems".
You can also check the Wikipedia article https://en.wikipedia.org/wiki/Convergence_of_random_variables
Many researchers have worked and are still working on the analysis of convergence of (stochastic) algorithms using tools for dynamical systems theory. You may check the works by Lessard, Scherer, Ebenbauer, Hu, Seiler, Rantzer, etc.
