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

DOI10.1007/S00440-014-0579-3MaRDI QIDQ495552zbMATH OpenOpenAlexWikidataFDO

Authors Radosław Adamczak, Paweł Wolff

Publication date 14 September 2015

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1304.1826

zbMATH Keywords

Sobolev inequalitiesconcentration of measureGaussian chaos

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Applications of functional analysis in probability theory and statistics (46N30) Random matrices (probabilistic aspects) (60B20) Inequalities; stochastic orderings (60E15)

Abstract: Building on the inequalities for homogeneous tetrahedral polynomials in independent Gaussian variables due to R. Lata{l}a we provide a concentration inequality for non-necessarily Lipschitz functions $fcolon{R}^{n}oR$ with bounded derivatives of higher orders, which hold when the underlying measure satisfies a family of Sobolev type inequalities $|g-Eg{|}_{p}leC(p)|ablag{|}_p.$ Such Sobolev type inequalities hold, e.g., if the underlying measure satisfies the log-Sobolev inequality (in which case $C(p)leCsqrtp$) or the Poincar'e inequality (then $C(p)leCp$). Our concentration estimates are expressed in terms of tensor-product norms of the derivatives of $f$. When the underlying measure is Gaussian and $f$ is a polynomial (non-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 ErdH{o}s-R{'e}nyi random graphs, obtaining new estimates, optimal in a certain range of parameters.

Recommendations

• Concentration inequalities for bounded functionals via log-Sobolev-type inequalities
• On some Gaussian concentration inequality for non-Lipschitz functions
• Second order concentration via logarithmic Sobolev inequalities
• Higher order concentration of measure
• Concentration inequalities using the entropy method

Cites work

• scientific article; zbMATH DE number 1574596 (Why is no real title available?)
• scientific article; zbMATH DE number 3928048 (Why is no real title available?)
• scientific article; zbMATH DE number 3980111 (Why is no real title available?)
• scientific article; zbMATH DE number 53996 (Why is no real title available?)
• scientific article; zbMATH DE number 177379 (Why is no real title available?)
• scientific article; zbMATH DE number 194093 (Why is no real title available?)
• scientific article; zbMATH DE number 3545969 (Why is no real title available?)
• scientific article; zbMATH DE number 709355 (Why is no real title available?)
• scientific article; zbMATH DE number 1014176 (Why is no real title available?)
• scientific article; zbMATH DE number 2007664 (Why is no real title available?)
• scientific article; zbMATH DE number 2034510 (Why is no real title available?)
• scientific article; zbMATH DE number 2174437 (Why is no real title available?)
• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
• An introduction to random matrices
• Concentration and moment inequalities for polynomials of independent random variables
• Concentration inequalities using the entropy method
• Concentration of measures supported on the cube
• Concentration of multivariate polynomials and its applications
• Concentration of non‐Lipschitz functions and applications
• Decoupling inequalities for polynomial chaos
• Decoupling inequalities for the tail probabilities of multivariate \(U\)- statistics
• Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)
• Divide and conquer martingales and the number of triangles in a random graph
• Eigenvalue distribution of large random matrices
• Exponential integrability and transportation cost related to logarithmic Sobolev inequalities
• Gaussian Hilbert Spaces
• Hypercontraction methods in moment inequalities for series of independent random variables in normed spaces
• Le Cam's Inequality and Poisson Approximations
• Logarithmic Sobolev Inequalities and Concentration of Measure for Convex Functions and Polynomial Chaoses
• Measure concentration through non-Lipschitz observables and functional inequalities
• Modified logarithmic Sobolev inequalities and transportation inequalities
• Moment and tail estimates for multidimensional chaoses generated by symmetric random variables with logarithmically concave tails
• Moment estimates derived from Poincaré and logarithmic Sobolev inequalities
• Moment inequalities for functions of independent random variables
• Monotonicity properties of optimal transportation and the FKG and related inequalities
• New concentration inequalities in product spaces
• Nonlinear large deviations
• On Measure Concentration of Vector-Valued Maps
• On asymptotic behavior of multilinear eigenvalue statistics of random matrices
• On concentration of empirical measures and convergence to the semi-circle law
• On decoupling, series expansions, and tail behavior of chaos processes
• On the Performance of Clustering in Hilbert Spaces
• On the role of convexity in isoperimetry, spectral gap and concentration
• On the variational problem for upper tails in sparse random graphs
• Poincaré's inequalities and Talagrand's concentration phenomenon for the exponential distribution
• Properties of isoperimetric, functional and transport-entropy inequalities via concentration
• Spectral analysis of large dimensional random matrices
• Tail and moment estimates for chaoses generated by symmetric random variables with logarithmically concave tails
• Tail and moment estimates for some types of chaos
• Tail and moment estimates for sums of independent random variables with logarithmically concave tails
• The Brunn-Minkowski inequality in Gauss space
• The concentration of measure phenomenon
• The free Markoff field
• The infamous upper tail
• The missing log in large deviations for triangle counts
• Tight upper tail bounds for cliques
• Transference principles for log-Sobolev and spectral-gap with applications to conservative spin systems
• Upper tails for subgraph counts in random graphs
• Upper tails for triangles
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)

Cited in

(50)

• On the convex Poincaré inequality and weak transportation inequalities
• Adaptive estimation of high-dimensional signal-to-noise ratios
• Concentration inequalities on the multislice and for sampling without replacement
• Model selection for high-dimensional linear regression with dependent observations
• Higher order concentration of measure
• Second-order concentration on the sphere
• scientific article; zbMATH DE number 34413 (Why is no real title available?)
• Moments of Gaussian chaoses in Banach spaces
• Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method
• Some notes on concentration for \(\alpha\)-subexponential random variables
• A variance-sensitive Gaussian concentration inequality
• The Hanson-Wright inequality for random tensors
• A note on concentration for polynomials in the Ising model
• On some Gaussian concentration inequality for non-Lipschitz functions
• Higher order concentration on Stiefel and Grassmann manifolds
• Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
• Concentration inequalities for some negatively dependent binary random variables
• Hanson-Wright inequality in Banach spaces
• Noncommutative martingale deviation and Poincaré type inequalities with applications
• A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
• scientific article; zbMATH DE number 7255152 (Why is no real title available?)
• Higher order concentration for functions of weakly dependent random variables
• Two-sided bounds for the tracial seminorm of multilinear Schur multipliers
• Concentration inequalities for bounded functionals via log-Sobolev-type inequalities
• Concentration inequalities for polynomials in \(\alpha\)-sub-exponential random variables
• Marchenko–Pastur law with relaxed independence conditions
• Moment estimates implied by modified log-Sobolev inequalities
• A counterexample to the DeMarco-Kahn upper tail conjecture
• Concentration inequalities for random tensors
• From \(p\)-Wasserstein bounds to moderate deviations
• Second order concentration via logarithmic Sobolev inequalities
• Concentration inequalities for separately convex functions
• Estimation of smooth functionals in normal models: bias reduction and asymptotic efficiency
• Estimation of the \(\ell_2\)-norm and testing in sparse linear regression with unknown variance
• Deviation inequality for monotonic Boolean functions with application to the number ofk-cycles in a random graph
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Concentration of non‐Lipschitz functions and applications
• Concentration for self-bounding functions and an inequality of Talagrand
• Upper tail bounds for cycles
• Higher order concentration in presence of Poincaré-type inequalities
• A spectral signature of breaking of ensemble equivalence for constrained random graphs
• High-probability bounds for the reconstruction error of PCA
• Concentration estimates for functions of finite high‐dimensional random arrays
• Sparse Hanson-Wright inequalities for subgaussian quadratic forms
• Isotonic regression meets Lasso
• Tensor-structured sketching for constrained least squares
• Subgaussian 1-cocycles on discrete groups
• Logarithmic Sobolev inequalities for finite spin systems and applications
• Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures

This page was built for publication: Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q495552)