# Martingale exit arguments for gradient Langevin dynamics

I am concerned about the proof of Lemma 6.3 (page 18) of this paper, https://arxiv.org/pdf/1902.08179.pdf which shows that for smooth convex functions the gradient Langevin dynamics has a high probability to be concentrated in a ball around the global minimum (say $$x^*$$).

Between equations 33-36 there seems to be happening a tricky use of Azuma-Hoeffding inequality that I dont seem to understand. Schematically this is what is happening : for a sequence of iterates/r.vs $$\{ X_i' \}$$, the authors define another sequence of r.vs $$\{ Y_i = \Vert X_i' - x^*\Vert^2 - iP \}$$ for some constant $$P>0$$ . Then the authors show that $$Y_{i+1} - Y_i \leq Q$$ for some constant $$Q>0$$. Now for some $$\lambda >0$$, they seem to want to do Azuma-Hoeffding to upperbound,

$$\mathbb{P} \left [ \sum_{k=1}^i (Y_{k} - Y_{k-1}) > \lambda \right ] \leq e^{-\frac{\lambda^2}{2Q}}$$

• How is this possible? Even if we believe that the difference sequence sequence, $$\{ Y_{i+1} - Y_i \}$$ satisfies the conditions for Azuma-Hoeffding to be applied to it, shouldn't the RHS be $$e^{-\frac{2\lambda^2}{iQ}}$$. Where is this $$i$$" in the exponent?

For concreteness I should state that I am using conventions about the Azuma-Hoeffding inequality as given in Corollary 3.9 (page 57) here https://web.math.princeton.edu/~rvan/APC550.pdf

• Secondly how do we know here that $$Y_{i+1} - Y_i$$ even satisfies the conditions for Azuma-Hoeffding to be applied? One sufficient condition is to show, (a) that this difference is bounded in absolute value and (b) that $$\mathbb{E} \left [ Y_{k} - Y_{k-1} \vert {\cal F}_{k-1} \right ] =0$$ where $${\cal F}_{k-1} = \sigma (\{ X_i \}_{i=0,\ldots,k-1})$$

Towards (a) we only seem to know that this difference is upperbounded and towads (b) we observe that here $$Y_k$$ is a function of $$X_{k}$$ and which in turn, because of the nature of gradient Langevin dynamics, is a function of all the iterates and injected noise till the $$(k-1)^{th}$$ iterate. So both $$Y_k$$ and $$Y_{k-1}$$ are $${\cal F}_{k-1}$$ measurable and hence $$\mathbb{E} \left [ Y_{k} - Y_{k-1} \vert {\cal F}_{k-1} \right ] = Y_k - Y_{k-1}$$ and thats not $$0$$. What am I missing?

• Maybe worth asking directly the authors? Sep 17 '19 at 15:50