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.

The union bound should now be clear.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.