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

DOI10.1007/S00440-014-0579-3zbMATH Open1323.60033arXiv1304.1826OpenAlexW2043065155WikidataQ59408615 ScholiaQ59408615MaRDI QIDQ495552FDOQ495552

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)

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.

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

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

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)

Cites Work

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

Cited In (50)

• A variance-sensitive Gaussian concentration inequality
• Two-sided bounds for the tracial seminorm of multilinear Schur multipliers
• 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
• Moments of Gaussian chaoses in Banach spaces
• Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method
• Title not available (Why is that?)
• Some notes on concentration for \(\alpha\)-subexponential random variables
• A note on concentration for polynomials in the Ising model
• The Hanson-Wright inequality for random tensors
• 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
• Title not available (Why is that?)
• A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
• Higher order concentration for functions of weakly dependent random variables
• 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
• From \(p\)-Wasserstein bounds to moderate deviations
• Concentration inequalities for random tensors
• 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
• Concentration of non‐Lipschitz functions and applications
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Upper tail bounds for cycles
• Concentration for self-bounding functions and an inequality of Talagrand
• Higher order concentration in presence of Poincaré-type inequalities
• A spectral signature of breaking of ensemble equivalence for constrained random graphs
• Concentration estimates for functions of finite high‐dimensional random arrays
• High-probability bounds for the reconstruction error of PCA
• Sparse Hanson-Wright inequalities for subgaussian quadratic forms
• Tensor-structured sketching for constrained least squares
• Subgaussian 1-cocycles on discrete groups
• Isotonic regression meets Lasso
• Logarithmic Sobolev inequalities for finite spin systems and applications
• Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures
• On the convex Poincaré inequality and weak transportation inequalities

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)