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

<p>The union bound should now be clear.</p>

CC BY-SA 4.0
2019-11-26T20:23:44.623Z
2019-11-26T20:23:44.623Z
Lad
<p>I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper <a href="https://arxiv.org/abs/1902.08179" rel="nofollow noreferrer">https://arxiv.org/abs/1902.08179</a>. Let me summarize the conceptual crux of the argument here using a slightly different notation than them. </p>

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

<p><span class="math-container">$$x_{t+1} = x_t - \eta_t (\nabla F(x_t) + \xi_{t,1}) + \sqrt{\eta_t} \xi_{t,2}$$</span></p>

<p>which starts from <span class="math-container">$x_0$</span> s.t <span class="math-container">$\Vert x_0 - x^* \Vert \leq r$</span> </p>

<p>Now they consider a coupled toy Markov chain <span class="math-container">$x'_t$</span> s.t <span class="math-container">$x'_0 = x_0$</span> and,</p>

<p><span class="math-container">$$\text{if } \Vert x_t' - x^* \Vert \geq r \text{ then } x'_{t+1} = x'_t  $$</span>
and <span class="math-container">$\text{if } \Vert x_t' - x^* \Vert &lt; 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} $</span></p>

<p>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 <span class="math-container">$r$</span> sized ball around the global minimum of the function. </p>

<ul>
<li>Now the main technical claim they make to relate the primed and the unprimed sequence is this : say the event <span class="math-container">$E := \{ \exists i \in \{1,\ldots,i_{\max}\} s.t \Vert x_i - x^*\Vert &gt; r\}$</span> then some curious union bounding is giving them,</li>
</ul>

<p><span class="math-container">$$\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 )$$</span></p>

<p>Can someone kindly explain why is the above inequality true?</p>

<lg.learning><stochastic-process><online-learning>
About estimating escape time of gradient Langevin dynamics
gradstudent
# About estimating escape time of gradient Langevin dynamics

(Asked by: username_0 on 2019-11-25)

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?

**Tags:** lg.learning, stochastic-process, online-learning


---

## 1 answers

### Answer by username_1 on 2019-11-26. Score: 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.


---

