-1
$\begingroup$

We have the following standard theorem : Let $X$ be some set and $g : X^n \rightarrow \mathbb{R}$ be a measurable function such that it satisfies the ``bounded difference property" i.e $\exists$ $\{c_i \geq 0\}_{i=1,..,n}$ s.t for each $i$ we have , $\sup _{x_1,..,x_n, x'_i \in X} \vert g(x_1,.,x_n) - g(x_1,..,x_i',..x_n)\vert \leq c_i $. Then the following is true, $\mathbb{P}[\vert Z - \mathbb{E}[Z] \vert >t] \leq 2e^{-\frac{t^2}{4\sum_{i=1}^nc_i^2}}$ i.e $\vert Z - \mathbb{E}[Z] \vert$ is sub-Gaussian.

  • Now how does the above standard theorem imply how the following inequality

$$\mathbb{E}[e^{\lambda (Z - \mathbb{E}[Z])}] \leq e^{\frac{\lambda^2 \sum_{i=1}^nc_i^2 }{2}}$$ $$?$$

Improve this question
$\endgroup$
1
  • $\begingroup$ What is $Z$ ? And what is the relevance of "bounded difference functions" ? The question seems to be: how to derive a bound on $\mathbb E e^{\lambda Z}$ from bounds on $\mathbb P[|Z|>t]$ for centered $Z$. $\endgroup$
    – Jean Duchon
    Commented Mar 28, 2018 at 7:19

2 Answers 2

Reset to default
2
$\begingroup$

The implication goes the other way. The "standard" inequality you quote, usually called McDiarmid's inequality is derived from the second inequality that you ask about. See e.g. http://empslocal.ex.ac.uk/people/staff/yy267/McDiarmid.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! Indeed it seems that the standard inequality I quoted is called the "McDiarmid Inequality" (somehow the reference I was reading didnt call it so! They presented it as an application of log-sobolev inequalities). But my question seems to be valid - that there is this specific consequence of McDiarmid inequality that can be proven (like what Iosif pointed out in his point 2). Am I missing something? $\endgroup$
    – gradstudent
    Commented Mar 28, 2018 at 15:02
1
$\begingroup$

$\newcommand{\ep}{\epsilon} \newcommand{\ga}{\gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}}$

As Yuval Peres pointed out, the implication usually goes the other way, from a bound on an exponential moment to a bound on the probability tail.

A few more points:

  1. Under your conditions, the constants in the exponents are actually better than yours: for $Z:=g(X_1,\dots,X_n)$ and independent $X_1,\dots,X_n$, we have \begin{equation} P(|Z -EZ| >t] \le 2e^{-\frac{2t^2}{c^2}} \end{equation} for $t\ge0$ and \begin{equation} Ee^{\la(Z -EZ)} \le e^{\la^2c^2/8}, \end{equation} where $c:=\sqrt{\sum_{i=1}^nc_i^2}$; see e.g. lecture notes.

  2. The best bound on $Ee^{\la(Z -EZ)}$ that you can get from your bound on the probability tail is as follows: for $X:=\la(Z -EZ)$ and $s:=\la c$, \begin{multline*} Ee^{\la(Z -EZ)}=Ee^X=\int_0^\infty P(e^X>t)dt=\int_{-\infty}^\infty P(X>u)e^u du \\ \le1+\int_0^\infty \min(1,2\exp\{-u^2/(4s^2)\}) e^u du \\ = 2 \sqrt{\pi } e^{s^2} s \left(\text{erf}\left(s-\sqrt{\ln2}\right)+1\right)+e^{2 s \sqrt{\ln2}} \sim 4 \sqrt{\pi } e^{s^2} s \end{multline*} as $s\to\infty$, vs. your supposed bound $e^{s^2/2}=e^{\frac{\la^2 \sum_{i=1}^nc_i^2 }{2}}$.

  3. Improved versions of McDiarmid's inequality are known; see e.g. Normal domination, especially Theorem 4.2 there.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks! So your calculation seems to be the direction of implication that I was asking about! The implication does seem to go in the same direction as I was asking about. Then what is the meaning of Yuval's comment about the inequality going the otherway? $\endgroup$
    – gradstudent
    Commented Mar 28, 2018 at 14:56
  • $\begingroup$ Given that you are getting a bigger upperbound does it mean that the inequality I wrote is wrong! (although the direction of inequality is right). The inequality I wrote is what seems to be happening at the bottom of page 8 (above remark 1) here, arxiv.org/pdf/1712.06541.pdf So this analysis in this paper is wrong? $\endgroup$
    – gradstudent
    Commented Mar 28, 2018 at 15:13
  • $\begingroup$ @gradstudent : Yuval's comment is of course correct: usually bounds on probability tails are obtained from bounds on the exponential moments, rather than vice versa -- as in your question. As shown in my answer, one can go in your reverse direction as well, getting then an "extra" factor $\asymp s$. $\endgroup$
    – Iosif Pinelis
    Commented Mar 28, 2018 at 15:33
  • $\begingroup$ @gradstudent : Nonetheless, your bound on the exponential moment is correct: as stated in my Point 1, even the better bound $Ee^{\lambda(Z -EZ)} \le e^{\lambda^2c^2/8}$ holds under the conditions stated there. Also, I guess you misunderstood what is written in the paper you referred to. I don't have the book by Boucheron et al (referred to in the paper) with me at the moment, but I think in the book they define the subgaussian condition in terms of exponential moments rather tails; or maybe they have both definitions, which are equivalent up to constants. $\endgroup$
    – Iosif Pinelis
    Commented Mar 28, 2018 at 15:42
  • $\begingroup$ Isnt the paper then basically doing what is in your second equation in point 1? (..And this bound on the expectation of the exponential of the r.v is what you say is stronger if obtained directly from the bouded difference condition rather than when derived from the tail bound on the deviation. Am I right?...) $\endgroup$
    – gradstudent
    Commented Mar 28, 2018 at 16:24

You must log in to answer this question.

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