15

Consider $X = \sum_i \lambda_i Y_i^2$, where $\lambda_i$ > 0 and $Y_i$ is distributed as a standard normal. What kind of concentration bounds can one prove on $X$, as a function of the (fixed) coefficients $\lambda_i$?

If all the $\lambda_i$ are equal then this is a Chernoff bound. The only other result I am aware of is a lemma from a paper of Arora and Kannan ("Learning mixtures of arbitrary Gaussians", STOC'01, Lemma 13), which proves concentration of the form $\Pr[X < E[X] - t] < \exp(-t^2/(4 \sum_i \lambda_i^2)$, i.e., the bound depends on the sum of the squares of the coefficients.

The proof of their lemma is analogous to the usual proof of the Chernoff bound. Are there other "canonical" such bounds, or a general theory of which functions of the $\lambda_i$'s are such that their largeness ensures good exponential concentration (here, the function was simply the sum of the squares)? Maybe some general measure of entropy?

A more standard reference for the Arora-Kannan lemma would also be great, if it exists.

Thomas
  • 445
  • 2
  • 7
  • How far did you get in reproducing their bound? This particular instance of the exponential mgf method seems to require some clever bounds and case analysis. – Thomas Ahle Jul 27 '17 at 10:06

1 Answers1

14

The book by Dubhashi and Panconesi collects together many such bounds, more numerous than can be listed here. If you find that hard to access immediately, there's an online survey of Chernoff-like bounds by Chung and Lu

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • Thanks, this looks very good. In particular, Theorem 3.5 of the Chung and Lu survey seems to be identical to the Arora-Kannan lemma I was stating. Having the sum of the lambda_i^2 appear is natural since it is simply the variance of X. – Thomas Aug 18 '10 at 03:56
  • 1
    The Chung and Lu link is dead. However, Internet Archive has it: http://web.archive.org/web/20070714095538/http://www.internetmathematics.org/volumes/3/1/ChungLu.pdf. The title is "Concentration Inequalities and Martingale Inequalities: A Survey" and the authors are Fan Chung and Linyuan Lu. – jbapple Mar 11 '17 at 09:54
  • 1
    Current link for Chung and Liu: https://doi.org/10.1080/15427951.2006.10129115 – Neal Young Jun 29 '20 at 11:46