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?

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.