Concentration inequalities for bounded functionals via generalized log-Sobolev inequalities

Abstract

In this paper we prove multilevel concentration inequalities for bounded functionals $f=f(X_1,\dots ,X_n)$ of random variables $X_1,\dots ,X_n$ that are either independent or satisfy certain logarithmic Sobolev inequalities. The constants in the tail estimates depend on the operator norms of $k$-tensors of higher order differences of $f$. We provide applications in both dependent and independent random variables. This includes deviation inequalities for empirical processes $f(X)={\sup }_{g\in \mathcal{F}}|g(X)|$ and suprema of homogeneous chaos in bounded random variables in the Banach space case given by $f(X)={\sup }_t\Vert {\sum }_{i_1\ne \dots \ne i_d}{t}_{i_1\dots i_d}{X}_{i_1}\cdots X_{i_d}{\Vert }_{\mathcal{B}}$. The latter application is comparable to earlier results of Boucheron-Bousquet-Lugosi-Massart and provides the upper tail bounds of Talagrand. In the case of Rademacher random variables, we give an interpretation of the results in terms of quantities familiar in Boolean analysis. Further applications are concentration inequalities for $U$-statistics with bounded kernels $h$ and for the number of triangles in an exponential random graph model.

arXiv commentchanged in v5: final version (restructured the article and several minor revisions; version accepted for publication at Journal of Theoretical Probability)

References in corpus (10)

• Estimating and understanding exponential random graph models
• Concentration around the mean for maxima of empirical processes
• Estimates of moments and tails of Gaussian chaoses
• Entropies, convexity, and functional inequalities
• Moment inequalities for functions of independent random variables
• Between Sobolev and Poincaré
• Moment inequalities for U-statistics
• Logarithmic Sobolev inequalities for finite spin systems and applications
• Higher Order Concentration of Measure
• A note on concentration for polynomials in the Ising model

Cited by in corpus (4)

• Concentration inequalities for polynomials in $\alpha$-sub-exponential random variables
• Logarithmic Sobolev inequalities for finite spin systems and applications
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Concentration inequalities on the multislice and for sampling without replacement