Bernstein-like Concentration and Moment Inequalities for Polynomials of Independent Random Variables: Multilinear Case

Abstract

We show that the probability that a multilinear polynomial $f$ of independent random variables exceeds its mean by $\lambda$ is at most $e^{-{\lambda }^2/(R^{q}Var(f))}$ for sufficiently small $\lambda$, where $R$ is an absolute constant. This matches (up to constants in the exponent) what one would expect from the central limit theorem. Our methods handle a variety of types of random variables including Gaussian, Boolean, exponential, and Poisson. Previous work by Kim-Vu and Schudy-Sviridenko gave bounds of the same form that involved less natural parameters in place of the variance.

arXiv admin note: substantial text overlap with arXiv:1104.4997

References in corpus (2)

• Efficient Optimal Learning for Contextual Bandits
• Estimates of moments and tails of Gaussian chaoses

Cited by in corpus (1)

• What Can ResNet Learn Efficiently, Going Beyond Kernels?