Given a function $f$ with a global minima at $x^*$, consider a stochastic process given as, $x_{t+1} = x_t - \nabla f(x_t) + \xi$ where $\xi$ is a random variable. Now we want to understand the occurrence of concentration of the following form ($\lambda >0$ is an arbitrary parameter and $x_0$ is an arbitrary choice of the starting point),
$$P \left [ \Vert x_T - x^* \Vert > {\cal O} \left ( \sqrt{ \lambda + T + \Vert x_0 - x^* \Vert^2 } \right ) \right ] \leq {\cal O} (T \cdot e^{-\frac{\lambda^2}{T}}) $$
I know of explicit examples of such phenomenon i.e of the process after time $t$ being spread out about the global minima of $f$ upto a distance of $\sqrt{{\rm t}}$.
- Is this kind of spreading the generic behaviour or the exception?
- Are there large classes of $f$ known for which this $\sqrt{{\rm time}}$ spreading about the global minima is known to hold?
