most recent 30 from http://mathoverflow.net 2013-05-26T07:39:23Z http://mathoverflow.net/feeds/question/47661 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/47661/concentration-bound-using-azumas-inequality-and-law-of-total-probability Pan Peng 2010-11-29T10:12:56Z 2010-11-29T11:38:28Z

<p>Given a function $f(X_1,\cdots,X_n,Y)$ on random variables ${X_i}$ and $Y$, which is continuous , I want to show that $f$ concentrates around its expectation $\operatorname*{E}[f]$, i.e., a formula like this: $\Pr[|f(X_1,\cdots,X_n, Y)-\operatorname*{E}[f(X_1,\cdots,X_n, Y)]|\geq t]\leq \exp(-\frac{t^2}{2c^2})$, where $c^2$ is the Lipschitz-type bound on $f$.</p> <p>The case considered here is different from the traditional one which does not have the additional continous random variable $Y$. However, we can still use the traditional way to show the concentration. By the Law of total probability, it is equal to bound $\operatorname*{E}_Y[\Pr[|f(X_1,\cdots,X_n, y)-\operatorname*{E}[f(X_1,\cdots,X_n, y)]|\geq t|Y=y]] \qquad (1)$.</p> <p>Given $y$ , if we have that $|\operatorname*{E}[f|X_1,\cdots,X_{i-1},X_i=x_i,y]-|\operatorname*{E}[f|X_1,\cdots,X_{i-1},X_i=x'_i, y]\leq c_i(y),$ for all $i$ with $1\leq i\leq n$ and any $x_i,x'_i$.</p> <p>then by the stardard use of Azuma's inequality, $\Pr[|f(X_1,\cdots,X_n, y)-\operatorname*{E}[f(X_1,\cdots,X_n, y)]|\geq t|Y=y]\leq \exp(-\frac{t^2}{2\sum_{i=1}^n c_i^2(y)})$.</p> <p>Thus, from (1), $\Pr[|f(X_1,\cdots,X_n, Y)-\operatorname*{E}[f(X_1,\cdots,X_n, Y)]|\geq t]\leq \operatorname*{E}[\exp(-\frac{t^2}{2\sum_{i=1}^n c_i^2(Y)})] \qquad (2)$</p> <p>My question is that can the above inequality be improved as: $\Pr[|f(X_1,\cdots,X_n, Y)-\operatorname*{E}[f(X_1,\cdots,X_n, Y)]|\geq t]\leq \exp(-\frac{t^2}{2\sum_{i=1}^n \operatorname*{E}[c_i(Y)]^2}) \qquad (3)$.</p> <p>P.S. I think that the Jassen's inequality (i.e., $\operatorname*E[g(Z)]\geq g(\operatorname*E[Z])$ for convex function $g$) may be useful here, but I donot see the convexity of the right hand of inequality (2). </p>

http://mathoverflow.net/questions/47661/concentration-bound-using-azumas-inequality-and-law-of-total-probability/47665#47665 Gideon Schechtman 2010-11-29T11:38:28Z 2010-11-29T11:38:28Z

<p>See my comment above for some problem in your argument but anyhow (3) is wrong. If the $X_i$-s are constants then the right hand side of (3) is 0, while the left hand side is not in general. If you don't like to use constant r.v.: if each of the $X_i$ takes values in a small interval, the right hand side is arbitrarily close to zero while the left hand side not, in general (say, for the function $f(x_1,...,x_n,y)=y$ and any reasonable $Y$).</p>