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?

  • $\begingroup$ Maybe worth asking directly the authors? $\endgroup$
    – Clement C.
    Sep 17 '19 at 15:50

Your Answer

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

Browse other questions tagged or ask your own question.