15
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jul 27, 2017 at 10:06

1 Answer 1

14
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Thomas
    Aug 18, 2010 at 3:56
  • 1
    $\begingroup$ The Chung and Lu link is dead. However, Internet Archive has it: web.archive.org/web/20070714095538/http://…. The title is "Concentration Inequalities and Martingale Inequalities: A Survey" and the authors are Fan Chung and Linyuan Lu. $\endgroup$
    – jbapple
    Mar 11, 2017 at 9:54
  • 1
    $\begingroup$ Current link for Chung and Liu: doi.org/10.1080/15427951.2006.10129115 $\endgroup$
    – Neal Young
    Jun 29, 2020 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.