Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order

By Radosław Adamczak, Pawel Wolff. 2013

114 citations recorded by the source corpus.

Building on the inequalities for homogeneous tetrahedral polynomials in independent Gaussian variables due to R. Latała we provide a concentration inequality for not necessarily Lipschitz functions $$f:\mathbb {R}^n \rightarrow \mathbb {R}$$f:Rn→R with bounded derivatives of higher orders, which holds when the underlying measure satisfies a family of Sobolev type inequalities $$\begin{aligned} \Vert g- \mathbb Eg\Vert _p \le C(p)\Vert \nabla g\Vert _p. \end{aligned}$$‖g-Eg‖p≤C(p)‖∇g‖p.Such Sobolev type inequalities hold, e.g., if the underlying measure satisfies the log-Sobolev inequality (in which case $$C(p) \le C\sqrt{p}$$C(p)≤Cp) or the Poincaré inequality (then $$C(p) \le Cp$$C(p)≤Cp). Our concentration estimates are expressed in terms of tensor-product norms of the derivatives of $$f$$f. When the underlying measure is Gaussian and $$f$$f is a polynomial (not necessarily tetrahedral or homogeneous), our estimates can be reversed (up to a constant depending only on the degree of the polynomial). We also show that for polynomial functions, analogous estimates hold for arbitrary random vectors with independent sub-Gaussian coordinates. We apply our inequalities to general additive functionals of random vectors (in particular linear eigenvalue statistics of random matrices) and the problem of counting cycles of fixed length in Erdős–Rényi random graphs, obtaining new estimates, optimal in a certain range of parameters.

Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f2b5b9e356164fd5ec4102ed49ba98d15685074d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Concentration inequalities for random tensors (2019, unknown): “Adamczak and Wolff [7] considered distributions that satisfy a Sobolev inequality, and he gave an extension of (1.5) for general differentiable functions of X (not just polynomials).”
Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method (2018, background): “Similarly, one can introduce the moment analog of logarithmic Sobolev inequality (see equation 3 in Adamczak and Wolff (2015)): ‖Z(X) − EZ(X)‖Lq ≤ K √ q‖|∇Z(X)|‖Lq , where K > 0 is a constant, | · | stands for the standard Euclidian norm and q ≥ 2.”
Concentration inequalities for polynomials in α-sub-exponential random variables (2019, methodology): “ones from [22] and [4] (among others).”
Hanson-Wright inequality and sub-gaussian concentration (2013, methodology): “Large deviation inequalities for polynomials of higher degree, which extend the Hanson-Wright type inequalities, have been obtained by Latala [11] and recently by Adamczak and Wolff [1].”
Better Agnostic Clustering Via Relaxed Tensor Norms (2017, methodology): “[AW15] show that these inequalities also hold for Poincaré distributions.”
A note on the Hanson-Wright inequality for random vectors with dependencies (2014, background): “Lata la provided also two-sided moment and tail inequalities for higher degree homogeneous forms in Gaussian variables [17] (see also [3]).”
Noncommutative martingale deviation and Poincaré type inequalities with applications (2012, background): “In the classical diffusion setting, Bakry and Emery [5] showed that the Γ2-criterion implies logarithmic Sobolev inequality, which in turn yields the Lp Poincaré inequalities with constant C √ p due to Aida and Stroock [2]; see also [1] for another proof.”
A Unified Theory of Confidence Regions and Testing for High-Dimensional Estimating Equations (2015, methodology): “We make usage of Theorem 1.4 of Adamczak and Wolff (2015), which provides a convenient concentration bound for higher moments of sub-Gaussian random variables.”