Does Pinelis' inequality (1994) exist?

Question

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?

I am reading this paper : https://arxiv.org/pdf/1803.08917.pdf. At Lemma 2.4 — K.J Fogang Fokoa, Nov 03 '20 at 10:58
This is the same as Azuma https://en.wikipedia.org/wiki/Azuma%27s_inequality, isn't it? — RaphaelB4, Nov 06 '20 at 07:46
It is not the same as Azuma. Pinelis' inequality holds in any dimension (in fact, in Hilbert space) with no dependence on dimension. — Yuval Peres, Nov 10 '20 at 05:39

score 84 · Accepted Answer · answered Nov 03 '20 at 13:51

84

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$.

answered Nov 03 '20 at 13:51

Iosif Pinelis

116,648

13

OHHH ! Okay Sir ! – K.J Fogang Fokoa Nov 03 '20 at 14:05
105

One of the things that I always liked about MathOverflow is the non-vanishing probability of getting first-hand anwers... :-) – Jochen Glueck Nov 03 '20 at 14:35
8

@JochenGlueck My personal favorite example. – Noah Schweber Nov 06 '20 at 01:18

Does Pinelis' inequality (1994) exist?

1 Answers1