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

• 成果类型: Article
• 署名作者: Adamczak, Radoslaw; Wolff, Pawel
• 署名单位: University of Warsaw; Polish Academy of Sciences; Institute of Mathematics of the Polish Academy of Sciences
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-014-0579-3
• 发表日期: 2015
• 页码: 531-586
• 关键词: independent random-variables; moment inequalities; decoupling inequalities; sobolev inequalities; tail probabilities; spectral-gap; transportation; POLYNOMIALS; sums

摘要

Building on the inequalities for homogeneous tetrahedral polynomials in independent Gaussian variables due to R. Lataa we provide a concentration inequality for not necessarily Lipschitz functions with bounded derivatives of higher orders, which holds when the underlying measure satisfies a family of Sobolev type inequalities Such Sobolev type inequalities hold, e.g., if the underlying measure satisfies the log-Sobolev inequality (in which case ) or the Poincar, inequality (then ). Our concentration estimates are expressed in terms of tensor-product norms of the derivatives of . When the underlying measure is Gaussian and 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 ErdAs-R,nyi random graphs, obtaining new estimates, optimal in a certain range of parameters.