Concentration inequalities using the entropy method

DOI10.1214/aop/1055425791zbMath1051.60020OpenAlexW1964718108WikidataQ58374469 ScholiaQ58374469MaRDI QIDQ1431503

Pascal Massart, Gábor Lugosi, Stéphane Boucheron

Publication date: 10 June 2004

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://projecteuclid.org/euclid.aop/1055425791

zbMATH Keywords

logarithmic Sobolev inequalityempirical processesrandom graphsconcentration inequalitiesRademacher chaosRademacher averages

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Combinatorial probability (60C05) Measures and integrals in product spaces (28A35)

Related Items

Concentration for Poisson functionals: component counts in random geometric graphs ⋮ Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices ⋮ Complexity regularization via localized random penalties ⋮ Stein's method for concentration inequalities ⋮ The missing log in large deviations for triangle counts ⋮ Rigorous verification, validation, uncertainty quantification and certification through concentration-of-measure inequalities ⋮ A NONPARAMETRIC ESTIMATOR FOR THE COVARIANCE FUNCTION OF FUNCTIONAL DATA ⋮ Threshold for monotone symmetric properties through a logarithmic Sobolev inequality ⋮ A tail bound for read-kfamilies of functions ⋮ Modified log-Sobolev inequalities and two-level concentration ⋮ Suprema of Chaos Processes and the Restricted Isometry Property ⋮ Extension complexity of low-dimensional polytopes ⋮ The restricted isometry property for time-frequency structured random matrices ⋮ Estimating the joint distribution of independent categorical variables via model selection ⋮ The empirical cost of optimal incomplete transportation ⋮ Applications of Stein's method for concentration inequalities ⋮ Upper tails for arithmetic progressions in random subsets ⋮ On randomized trace estimates for indefinite matrices with an application to determinants ⋮ Uniform concentration inequality for ergodic diffusion processes ⋮ Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method ⋮ Generalizations of some probability inequalities and \(L^{p}\) convergence of random variables for any monotone measure ⋮ Moderate deviations in cycle count ⋮ Restricted isometries for partial random circulant matrices ⋮ Thermodynamics and concentration ⋮ Lower large deviations and laws of large numbers for maximal flows through a box in first passage percolation ⋮ Central moment inequalities using Stein's method ⋮ Rates of convergence for partial mass problems ⋮ Detecting local network motifs ⋮ Stochastic Convergence of a Nonconforming Finite Element Method for the Thin Plate Spline Smoother for Observational Data ⋮ Multiscale functional inequalities in probability: constructive approach ⋮ An improved analysis of the Rademacher data-dependent bound using its self bounding property ⋮ A randomly weighted minimum spanning tree with a random cost constraint ⋮ Symmetrization approach to concentration inequalities for empirical processes. ⋮ Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order ⋮ A Bernstein-type inequality for functions of bounded interaction ⋮ Transport inequalities for random point measures ⋮ Local tail bounds for functions of independent random variables ⋮ Uncertainty quantification via codimension-one partitioning ⋮ Aspects of discrete mathematics and probability in the theory of machine learning ⋮ Dominated concentration ⋮ On some random thin sets of integers ⋮ Optimal quantitative estimates in stochastic homogenization for elliptic equations in nondivergence form ⋮ Law of large numbers for the maximal flow through tilted cylinders in two-dimensional first passage percolation ⋮ Moment inequalities for functions of independent random variables ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Second order concentration via logarithmic Sobolev inequalities ⋮ Arbitrary Threshold Widths for Monotone, Symmetric Properties ⋮ Exponential concentration for first passage percolation through modified Poincaré inequalities ⋮ Concentration inequalities for measures of a Boolean model ⋮ Concentration inequalities for bounded functionals via log-Sobolev-type inequalities ⋮ Limit theorems for eigenvectors of the normalized Laplacian for random graphs ⋮ Theory of Classification: a Survey of Some Recent Advances ⋮ Concentration inequalities for dependent random variables via the martingale method ⋮ From Steiner formulas for cones to concentration of intrinsic volumes ⋮ Parametric estimation. Finite sample theory ⋮ On the Optimality of Sample-Based Estimates of the Expectation of the Empirical Minimizer ⋮ Multiple choice tries and distributed hash tables ⋮ Optimal graphon estimation in cut distance ⋮ A smooth approach to Malliavin calculus for Lévy processes ⋮ The choice of representative volumes in the approximation of effective properties of random materials ⋮ Modified log-Sobolev inequalities, Beckner inequalities and moment estimates ⋮ Finer estimates on the \(2\)-dimensional matching problem ⋮ Concentration inequalities on the multislice and for sampling without replacement ⋮ Unnamed Item ⋮ Local Rademacher complexities ⋮ Entropy and Concentration ⋮ Fluctuation estimates for the multi-cell formula in stochastic homogenization of partitions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On general minimax theorems
• An Efron-Stein inequality for nonsymmetric statistics
• The jackknife estimate of variance
• On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures
• Information inequalities and concentration of measure
• A Bennett concentration inequality and its application to suprema of empirical processes
• Empirical margin distributions and bounding the generalization error of combined classifiers
• About the constants in Talagrand's concentration inequalities for empirical processes.
• Concentration of measure and isoperimetric inequalities in product spaces
• Weak convergence and empirical processes. With applications to statistics
• A measure concentration inequality for contracting Markov chains
• A new look at independence
• Bounding \(\bar d\)-distance by informational divergence: A method to prove measure concentration
• The deletion method for upper tail estimates
• On the Choice Number of Random Hypergraphs
• On Talagrand's deviation inequalities for product measures
• A simple proof of the blowing-up lemma (Corresp.)
• Bounds on conditional probabilities with applications in multi-user communication
• A sharp concentration inequality with applications
• On the concentration of multivariate polynomials with small expectation
• The infamous upper tail
• Some applications of concentration inequalities to statistics
• Concentration inequalities for set-indexed empirical processes
• Concentration of multivariate polynomials and its applications
• Model selection and error estimation
• New concentration inequalities in product spaces