Concentration of measure and isoperimetric inequalities in product spaces

DOI10.1007/BF02699376MaRDI QIDQ1908323zbMATH OpenWikidataFDO

Authors Michel Talagrand

Publication date 3 June 1997

Published in Publications Mathématiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9406212, http://www.numdam.org/item?id=PMIHES_1995__81__73_0, https://eudml.org/doc/104106

zbMATH Keywords

martingale methodsSherrington-Kirkpatrick modelconcentration functionconcentration of measure phenomenonsums of Banach space-valued independent random variables

Mathematics Subject Classification ID

Gaussian processes (60G15) Geometric probability and stochastic geometry (60D05) Inequalities; stochastic orderings (60E15) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Stochastic processes (60G99) Measures and integrals in product spaces (28A35) Probabilistic measure theory (60A10)

Abstract: The concentration of measure prenomenon roughly states that, if a set $A$ in a product $Omeg{a}^N$ of probability spaces has measure at least one half, ``most of the points of $Omeg{a}^N$ are ``close to $A$. We proceed to a systematic exploration of this phenomenon. The meaning of the word ``most is made rigorous by isoperimetric-type inequalities that bound the measure of the exceptional sets. The meaning of the work ``close is defined in three main ways, each of them giving rise to related, but different inequalities. The inequalities are all proved through a common scheme of proof. Remarkably, this simple approach not only yields qualitatively optimal results, but, in many cases, captures near optimal numerical constants. A large number of applications are given, in particular in Percolation, Geometric Probability, Probability in Banach Spaces, to demonstrate in concrete situations the extremely wide range of application of the abstract tools.

Recommendations

• A concentration inequality for product spaces
• An isoperimetric inequality for Gauss-like product measures
• On the isoperimetric constants for product measures
• scientific article; zbMATH DE number 2034507
• On measure concentration for separately Lipschitz functions in product spaces
• New concentration inequalities in product spaces
• Concentration of product spaces
• Isoperimetry for product of probability measures: recent results
• On isoperimetric profiles of product spaces
• Poincare inequalities, isoperimetric estimates, and representation formulas on product spaces

Cites work

• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 4043612 (Why is no real title available?)
• scientific article; zbMATH DE number 18577 (Why is no real title available?)
• scientific article; zbMATH DE number 18980 (Why is no real title available?)
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 177377 (Why is no real title available?)
• scientific article; zbMATH DE number 3618783 (Why is no real title available?)
• scientific article; zbMATH DE number 742989 (Why is no real title available?)
• A Topological Application of the Isoperimetric Inequality
• A matching problem and subadditive Euclidean functionals
• A new isoperimetric inequality for product measure and the tails of sums of independent random variables
• A sharp deviation inequality for the stochastic traveling salesman problem
• An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Characterization of the law of the iterated logarithm in Banach spaces
• Exponential Bounds for Large Deviations
• Inequalities for bin packing-III
• Isoperimetry and integrability of the sum of independent Banach-space valued random variables
• New concentration inequalities in product spaces
• On the Expected Value of a Random Assignment Problem
• On the Fluctuations of the Stochastic Traveling Salesperson Problem
• On the fluctuations of simple matching
• On the length of the longest monotone subsequence in a random permutation
• On the speed of convergence in first-passage percolation
• Optimal numberings and isoperimetric problems on graphs
• Poisson approximation for large deviations
• Probability Inequalities for Sums of Bounded Random Variables
• Regularity of infinitely divisible processes
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Some deviation inequalities
• Some rigorous results on the Sherrington-Kirkpatrick spin glass model.
• The Sherrington-Kirkpatrick model of spin glasses and stochastic calculus: The high temperature case
• The Supremum of Some Canonical Processes
• The chromatic number of random graphs
• The chromatic number of random graphs
• The distribution of vector-valued Rademacher series
• The height of a random partial order: Concentration of measure
• The probabilistic method
• Unconditional and symmetric sets in \(n\)-dimensional normed spaces

Cited in

(only showing first 100 items - show all)

• Shadows of ordered graphs
• Blessing of dimensionality: mathematical foundations of the statistical physics of data
• Properties of the parabolic Anderson model and the Anderson polymer model
• Second order accurate distributed eigenvector computation for extremely large matrices
• Isoperimetric inequality on a metric measure space and Lipschitz order with an additive error
• Entropic curvature on graphs along Schrödinger bridges at zero temperature
• Greedy lattice animals: Negative values and unconstrained maxima
• Modular statistics for subgraph counts in sparse random graphs
• Estimate of observable diameter of \(l_p\)-product spaces
• Concentration inequalities for Poisson point processes with application to adaptive intensity estimation
• Free energies of Boltzmann machines: self-averaging, annealed and replica symmetric approximations in the thermodynamic limit
• Second order concentration via logarithmic Sobolev inequalities
• Functional inequalities for two-level concentration
• Outliers in spectrum of sparse Wigner matrices
• Quadratic transportation cost inequality for scalar stochastic conservation laws
• PDE/statistical mechanics duality: relation between Guerra's interpolated \(p\)-spin ferromagnets and the Burgers hierarchy
• Minimum cost matching in a random graph with random costs
• Phase transitions in normalized cut of social networks
• The Legendre transform of two replicas of the Sherrington-Kirkpatrick spin glass model
• The radial spanning tree of a Poisson point process
• The Bennett-Orlicz norm
• A note on transportation cost inequalities for diffusions with reflections
• Quenched central limit theorem in a corner growth setting
• Quantitative estimates for the flux of TASEP with dilute site disorder
• Modified log-Sobolev inequality for a compact pure jump Markov process with degenerate jumps
• Modified log-Sobolev inequalities and two-level concentration
• A note on concentration for polynomials in the Ising model
• Upper tails via high moments and entropic stability
• Deviation inequality for monotonic Boolean functions with application to the number ofk-cycles in a random graph
• Delocalization of polymers in lower tail large deviation
• Concentration inequalities via zero bias couplings
• Weak monotone rearrangement on the line
• Coalescence of Euclidean geodesics on the Poisson-Delaunay triangulation
• Applications of weak transport theory
• Maxima and near-maxima of a Gaussian random assignment field
• The planted matching problem: phase transitions and exact results
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• The structure of low-complexity Gibbs measures on product spaces
• Fluctuations of transverse increments in two-dimensional first passage percolation
• Concentration inequalities for empirical processes of linear time series
• Phase transition in spectral clustering based on resistance matrix
• Functional linear regression with Huber loss
• Concentration inequalities on the multislice and for sampling without replacement
• Rumor spreading on random regular graphs and expanders
• Kloosterman paths and the shape of exponential sums
• On Bernstein type inequalities for stochastic integrals of multivariate point processes
• Absence of mutual unbounded growth for almost all parameter values in the two-type Richardson model.
• A general method for lower bounds on fluctuations of random variables
• Sublinearity of the number of semi-infinite branches for geometric random trees
• Large deviations of the range of the planar random walk on the scale of the mean
• Competition interfaces and second class particles
• Circular law theorem for random Markov matrices
• Concentration inequalities and limit theorems for randomized sums
• Variational bounds for the generalized random energy model
• A Hsu-Robbins-Erdős strong law in first-passage percolation
• Exponential concentration for first passage percolation through modified Poincaré inequalities
• Rigorous results for mean field models for spin glasses
• Random walks on quasirandom graphs
• Exponential integrability and transportation cost related to logarithmic Sobolev inequalities
• Moment inequalities for functions of independent random variables
• Spectrum of non-Hermitian heavy tailed random matrices
• Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
• Picker-chooser fixed graph games
• Merging percolation onZdand classical random graphs: Phase transition
• Concentration inequalities for functions of independent variables
• Central limit theorem for first-passage percolation time across thin cylinders
• scientific article; zbMATH DE number 177377 (Why is no real title available?)
• Randomly colouring graphs (a combinatorial view)
• Signal propagation in small-world biological networks with weak noise
• Modified logarithmic Sobolev inequalities and transportation inequalities
• A central limit theorem for the overlap in the Hopfield model
• An approximate vertex-isoperimetric inequality for \(r\)-sets
• Constructive bounds for a Ramsey-type problem
• Applications of Stein's method for concentration inequalities
• scientific article; zbMATH DE number 1523257 (Why is no real title available?)
• On the concentration of eigenvalues of random symmetric matrices
• The concentration of measure phenomenon
• Around the circular law
• On the existence and nonexistence of finitary codings for a class of random fields
• Complexity measures of sign matrices
• Bounding \(\bar d\)-distance by informational divergence: A method to prove measure concentration
• A stronger bound for the strong chromatic index
• A Bernstein-type inequality for suprema of random processes with applications to model selection in non-Gaussian regression
• From the Prékopa-Leindler inequality to modified logarithmic Sobolev inequality
• Detecting positive correlations in a multivariate sample
• Concentration inequalities, large and moderate deviations for self-normalized empirical processes
• Concentration of measure inequalities for Markov chains and \(\Phi\)-mixing processes.
• Fluctuations of the free energy in the REM and the \(p\)-spin SK models
• The missing log in large deviations for triangle counts
• A measure concentration inequality for contracting Markov chains
• About the constants in Talagrand's concentration inequalities for empirical processes.
• Concentration of Haar measures, with an application to random matrices
• On the geometry of similarity search: dimensionality curse and concentration of measure
• A bound on the strong chromatic index of a graph
• A Fourier view on the \(R\)-transform and related asymptotics of spherical integrals
• Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry
• Concentration of norms and eigenvalues of random matrices
• Local tail bounds for functions of independent random variables
• Ramsey-Milman phenomenon, Urysohn metric spaces, and extremely amenable groups
• Concentration of measure and spectra of random matrices: applications to correlation matrices, elliptical distributions and beyond

This page was built for publication: Concentration of measure and isoperimetric inequalities in product spaces

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