About estimating escape time of gradient Langevin dynamics

Question

I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper https://arxiv.org/abs/1902.08179. Let me summarize the conceptual crux of the argument here using a slightly different notation than them.

Here we are given $F : \mathbb{R}^d \rightarrow \mathbb{R}$ a convex, differentiable and $L-$smooth function with a minimizer at $x^*$ and 3 constants : $r$ and $C_\xi$ and $i_{max}$ (a positive integer). Now for $\xi_{t,1}$ a sequence of bounded random variables and $\xi_{t,2}$ a sequence of Normally distributed random variables we have the following dynamics happening,

$$x_{t+1} = x_t - \eta_t (\nabla F(x_t) + \xi_{t,1}) + \sqrt{\eta_t} \xi_{t,2}$$

which starts from $x_0$ s.t $\Vert x_0 - x^* \Vert \leq r$

Now they consider a coupled toy Markov chain $x'_t$ s.t $x'_0 = x_0$ and,

$$\text{if } \Vert x_t' - x^* \Vert \geq r \text{ then } x'_{t+1} = x'_t $$ and $\text{if } \Vert x_t' - x^* \Vert < r \text{ then } x'_{t+1} = x'_t - \eta_t (\nabla F(x_t') + \xi_{t,1}) + \sqrt{\eta_t} \min (C_\xi, \Vert \xi_{t,2} \Vert) \frac{\xi_{t,2}}{\Vert \xi_{t,2} \Vert} $

Hence it seems that the primed sequence is designed s.t it never comes back into the ball once it leaves the interior of the $r$ sized ball around the global minimum of the function.

• Now the main technical claim they make to relate the primed and the unprimed sequence is this : say the event $E := \{ \exists i \in \{1,\ldots,i_{\max}\} s.t \Vert x_i - x^*\Vert > r\}$ then some curious union bounding is giving them,

$$\mathbb{P} \left [ E \right ] \leq \sum_{i=1}^{i_{max}} \left ( \mathbb{P} [\Vert x_i'-x^*\Vert^2 \geq r^2] + \mathbb{P} [ \Vert \xi_{i,2} \Vert \geq C_\xi ] \right )$$

Can someone kindly explain why is the above inequality true?

Answer 1

Observe that the following event contains your event $E$: either (1) for some $i$, $\|\xi_{i,2}\| > C_{\zeta}$ (in which case $x_{i+1}$ and $x_{i+1}'$ are no longer the same), or (2) for some $i$, $x_i'$ leaves the ball. It might be easier to see containment (in the opposite direction) of the complement events: if for all $i$ both $\|\xi_{i,2}\| \le C_{\xi}$ and also $x_i'$ is inside the ball, this surely means that $x_i=x_i'$ for all $i$ and hence also $x_i$ is always inside the ball.

The union bound should now be clear.