Discrete Mathematics and Optimization Seminar

---

Gabor Lugosi
Pompeu Fabra University
Monday September 26th at 4.30pm
Burnside 1205



Title. Concentration and moment inequalities for functions of independent random variables

Abstract. A general method for obtaining concentration inequalities for functions of independent random variables is presented. It is a generalization of the
entropy method which has been used to derive concentration inequalities for such functions, and is based on a generalized tensorization inequality
due to Latala and Oleszkiewicz.

The new inequalities prove to be a versatile tool in a wide range of applications. We illustrate the power of the method by showing how it can
be used to effortlessly re-derive classical inequalities including Rosenthal and Kahane-Khinchine-type inequalities for sums of independent
random variables, moment inequalities for suprema of empirical processes, and moment inequalities for Rademacher chaos and U-statistics. We also
provide examples involving random combinatorial entropies.

We generalize Talagrand's exponential inequality for Rademacher chaos of order two to any order. We also discuss applications for other complex
functions of independent random variables, such as suprema of boolean polynomials which include, as special cases, sub graph counting problems
in random graphs.
(Joint work with S. Boucheron, O. Bousquet, and P. Massart)