Concentration and moment inequalities for polynomials of independent random variables

Warren Schudy, Maxim Sviridenko

TL;DR

This paper introduces a powerful new method for proving concentration inequalities—mathematical guarantees that a random variable stays close to its average—specifically for polynomials of independent random variables. The authors' approach outperforms the classic Kim-Vu inequality, works for a much broader range of distributions (including Gaussian, Poisson, and Boolean), and remains effective even for high-degree polynomials with small expected values.

What Problem Does This Paper Address?

In fields like theoretical computer science and discrete mathematics, we often need to know how much a complex function of many random inputs fluctuates. For example, if you have a random graph, how much does the number of triangles in that graph deviate from the average?

While we have "Chernoff bounds" for simple sums of variables, functions like "triangle counts" are represented as polynomials. Proving concentration for polynomials is notoriously difficult. The previous gold standard, the Kim-Vu inequality, had several drawbacks:

  1. It was primarily designed for Bernoulli (0/1) variables.
  2. Its bounds depended on the total number of variables ($n$), which is suboptimal.
  3. It struggled with "high-degree" polynomials or cases where the expected value was very small.

Schudy and Sviridenko set out to create a more "universal" inequality that handles various distributions and provides tighter bounds that don't depend on $n$.

Methods

The authors move away from the standard "Moment Generating Function" (MGF) approach used in Chernoff-style bounds. For polynomials, the "tails" of the distribution can be too heavy, making the MGF infinite and the math break down.

Instead, they use the Method of Moments. They calculate the $k$-th moment of the polynomial and then apply Markov’s inequality. The heavy lifting involves:

  • Moment-Bounded Variables: They define a broad class of "moment-bounded" random variables (where the $i$-th moment is bounded by the $(i-1)$-th moment). This class is huge, covering Gaussian, Poisson, Binomial, and Exponential distributions.
  • Combinatorial Counting Lemma: To bound the $k$-th moment, they represent the polynomial as a weighted hypergraph. They developed a sophisticated "counting lemma" to estimate the number of ways hyperedges can overlap, which allows them to sum up the contributions to the total variance and higher-order moments.
  • Refined Smoothness Parameters: They use a tighter version of "average partial derivatives" to measure how much changing one input affects the total function.

Datasets

As a theoretical mathematics and probability paper, it does not use empirical datasets. Instead, the authors evaluate their method against:

  • Multilinear Polynomials: Functions where each variable appears at most to the first power in any term.
  • Permanents of Random Matrices: A notoriously difficult-to-calculate matrix property used as a benchmark for concentration.
  • Random Graphs: Specifically looking at subgraph counts (like triangles).

Key Insights and Ideas

  • Independence from $n$: One of the most significant "aha" moments is that the concentration of a polynomial depends on its degree and its "smoothness," but not necessarily on the total number of variables involved. This makes the bounds much more robust for massive systems.
  • The Power of Centering: The authors show that by "centering" the polynomials (subtracting the mean of each component), they can decompose complex functions into manageable pieces that obey strict combinatorial rules.
  • Tightness: The authors didn't just find a bound; they proved a "lower bound" (Theorem 1.3) showing that their inequality is essentially the best possible. Any further improvement would only be in the constant factors, not the fundamental scaling.

Key Results

  • Theorem 1.4 (The Main Result): Provides a general concentration inequality for any polynomial of moment-bounded variables. It shows that the probability of a deviation $\lambda$ decays exponentially.
  • Superiority over Kim-Vu: The authors demonstrate that their inequality is strictly stronger than the Kim-Vu result, particularly because it removes the $\log n$ factors that previously weakened the bounds.
  • Permanents: They provided the first non-trivial concentration results for the permanents of random symmetric matrices, a problem that was previously considered intractable using existing concentration tools.

Limitations and Future Work

  • The Degree Penalty: While the method handles high-degree polynomials better than previous ones, there is still an $R^q$ term in the exponent (where $q$ is the degree). For polynomials of very high degree, this constant $R$ can make the bound less "interesting" or practical.
  • Non-Independent Variables: The current work relies heavily on the independence of the input variables. Extending these "moment methods" to weakly dependent variables (like those found in Markov chains) remains an open challenge.
  • Complexity of Smoothness: Calculating the $\mu_r$ parameters (the smoothness measures) for a specific arbitrary polynomial can still be computationally intensive, even if the resulting bound is mathematically tight.

Summary updated

Abstract

In this work we design a general method for proving moment inequalities for polynomials of independent random variables. Our method works for a wide range of random variables including Gaussian, Boolean, exponential, Poisson and many others. We apply our method to derive general concentration inequalities for polynomials of independent random variables. We show that our method implies concentration inequalities for some previously open problems, e.g. permanent of random symmetric matrices. We show that our concentration inequality is stronger than the well-known concentration inequality due to Kim and Vu [29]. The main advantage of our method in comparison with the existing ones is a wide range of random variables we can handle and bounds for previously intractable regimes of high degree polynomials and small expectations. On the negative side we show that even for boolean random variables each term in our concentration inequality is tight.
BibTeX
@inproceedings{schudy2012concentration,
  author = {Warren Schudy and Maxim Sviridenko},
  title = {{Concentration and moment inequalities for polynomials of independent random variables}},
  booktitle = {SODA},
  year = {2012},
  url = {https://openreview.net/forum?id=vlOPSwZgCSmA},
}

Loading related content...

Figure