22
$\begingroup$

I am reading a paper on stochastic optimization. And in this paper, the proofs are based on the Pinelis' 1994 inequality. I read the paper by Pinelis for more information and it is with great frustration that I was not able to find the inequality corresponding to that mentioned in the paper I am reading.

Here's the inequality in the article I'm reading:

$$ \begin{array}l \text{(The Pinelis' 1994 inequality). Let } X_1,\dots, X_T \in \mathbb{R}^d \\ \text{be a random process satisfying } \mathbb{E}[X_t\mid X_1,\dots,X_{t−1} ] = 0 \text{ and} \\ \|X_t\| ≤ M. \text{ Then } \mathbb{P}[\| X_1 + \cdots + X_T\|^2 > 2 \log(2 /\delta)M^2T] \leq \delta. \end{array} $$

Nowhere in Pinelis' 1994 paper is this inequality mentioned.

So I ask myself, does this inequality really exist? Do you know it?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I am reading this paper : arxiv.org/pdf/1803.08917.pdf. At Lemma 2.4 $\endgroup$
    – K.J Fogang Fokoa
    Commented Nov 3, 2020 at 10:58
  • 17
    $\begingroup$ looks like theorem 3.5 in Pinelis (1994) $\endgroup$
    – Carlo Beenakker
    Commented Nov 3, 2020 at 12:37
  • $\begingroup$ This is the same as Azuma en.wikipedia.org/wiki/Azuma%27s_inequality, isn't it? $\endgroup$
    – RaphaelB4
    Commented Nov 6, 2020 at 7:46
  • 6
    $\begingroup$ It is not the same as Azuma. Pinelis' inequality holds in any dimension (in fact, in Hilbert space) with no dependence on dimension. $\endgroup$
    – Yuval Peres
    Commented Nov 10, 2020 at 5:39

1 Answer 1

Reset to default
88
$\begingroup$

As noted in Carlo Beenakker's comment, your inequality is a direct application of Theorem 3.5 in the linked paper: in that theorem, take $d_j=X_j$, $r=\sqrt{2M^2 T\ln(2/\delta)}$, $b_*^2=M^2T$, and $D=1$.

Improve this answer
$\endgroup$
3
  • 15
    $\begingroup$ OHHH ! Okay Sir ! $\endgroup$
    – K.J Fogang Fokoa
    Commented Nov 3, 2020 at 14:05
  • 112
    $\begingroup$ One of the things that I always liked about MathOverflow is the non-vanishing probability of getting first-hand anwers... :-) $\endgroup$
    – Jochen Glueck
    Commented Nov 3, 2020 at 14:35
  • 8
    $\begingroup$ @JochenGlueck My personal favorite example. $\endgroup$
    – Noah Schweber
    Commented Nov 6, 2020 at 1:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .