Concentration of measure and isoperimetric inequalities in product spaces

DOI10.1007/BF02699376zbMATH Open0864.60013arXivmath/9406212WikidataQ92174908 ScholiaQ92174908MaRDI QIDQ1908323FDOQ1908323

Michel Talagrand

Publication date: 3 June 1997

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

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.

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probability Inequalities for Sums of Bounded Random Variables
• New concentration inequalities in product spaces
• 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
• The probabilistic method
• The Sherrington-Kirkpatrick model of spin glasses and stochastic calculus: The high temperature case
• Optimal numberings and isoperimetric problems on graphs
• Some rigorous results on the Sherrington-Kirkpatrick spin glass model.
• A Topological Application of the Isoperimetric Inequality
• On the length of the longest monotone subsequence in a random permutation
• The height of a random partial order: Concentration of measure
• The chromatic number of random graphs
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• On the speed of convergence in first-passage percolation
• The chromatic number of random graphs
• The Supremum of Some Canonical Processes
• Poisson approximation for large deviations
• Isoperimetry and integrability of the sum of independent Banach-space valued random variables
• Some deviation inequalities
• A matching problem and subadditive Euclidean functionals
• Exponential Bounds for Large Deviations
• The distribution of vector-valued Rademacher series
• An Isoperimetric Theorem on the Cube and the Kintchine-Kahane Inequalities
• Regularity of infinitely divisible processes
• Unconditional and symmetric sets in \(n\)-dimensional normed spaces
• On the Expected Value of a Random Assignment Problem
• A sharp deviation inequality for the stochastic traveling salesman problem
• A new isoperimetric inequality for product measure and the tails of sums of independent random variables
• On the fluctuations of simple matching
• On the Fluctuations of the Stochastic Traveling Salesperson Problem
• Inequalities for bin packing-III

Cited In (only showing first 100 items - show all)

• Modified log-Sobolev inequality for a compact pure jump Markov process with degenerate jumps
• Functional linear regression with Huber loss
• Concentration inequalities on the multislice and for sampling without replacement
• Kloosterman paths and the shape of exponential sums
• Quenched central limit theorem in a corner growth setting
• Upper tails via high moments and entropic stability
• Modified log-Sobolev inequalities and two-level concentration
• Maxima and near-maxima of a Gaussian random assignment field
• On Bernstein type inequalities for stochastic integrals of multivariate point processes
• Functional inequalities for two-level concentration
• Absence of mutual unbounded growth for almost all parameter values in the two-type Richardson model.
• The Legendre transform of two replicas of the Sherrington-Kirkpatrick spin glass model
• A note on concentration for polynomials in the Ising model
• Shadows of ordered graphs
• Quantitative estimates for the flux of TASEP with dilute site disorder
• Self-organized segregation on the grid
• Rumor spreading on random regular graphs and expanders
• Isoperimetric inequality on a metric measure space and Lipschitz order with an additive error
• Greedy lattice animals: Negative values and unconstrained maxima
• The structure of low-complexity Gibbs measures on product spaces
• 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
• The radial spanning tree of a Poisson point process
• A general method for lower bounds on fluctuations of random variables
• Concentration inequalities for Poisson point processes with application to adaptive intensity estimation
• A note on transportation cost inequalities for diffusions with reflections
• Modular statistics for subgraph counts in sparse random graphs
• Blessing of dimensionality: mathematical foundations of the statistical physics of data
• Second order concentration via logarithmic Sobolev inequalities
• Outliers in spectrum of sparse Wigner matrices
• Delocalization of polymers in lower tail large deviation
• Title not available (Why is that?)
• Deviation inequality for monotonic Boolean functions with application to the number ofk-cycles in a random graph
• Phase transition in spectral clustering based on resistance matrix
• Properties of the parabolic Anderson model and the Anderson polymer model
• Second order accurate distributed eigenvector computation for extremely large matrices
• Phase transitions in normalized cut of social networks
• Applications of weak transport theory
• The planted matching problem: phase transitions and exact results
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Weak monotone rearrangement on the line
• Entropic curvature on graphs along Schrödinger bridges at zero temperature
• Estimate of observable diameter of \(l_p\)-product spaces
• Coalescence of Euclidean geodesics on the Poisson-Delaunay triangulation
• Fluctuations of transverse increments in two-dimensional first passage percolation
• Sublinearity of the number of semi-infinite branches for geometric random trees
• Minimum Cost Matching in a Random Graph with Random Costs
• Concentration inequalities via zero bias couplings
• Free energies of Boltzmann machines: self-averaging, annealed and replica symmetric approximations in the thermodynamic limit
• Large deviations of the range of the planar random walk on the scale of the mean
• On the existence and nonexistence of finitary codings for a class of random fields
• Some applications of concentration inequalities to statistics
• First passage percolation has sublinear distance variance.
• Second-order concentration on the sphere
• 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
• Picker-chooser fixed graph games
• Ramsey-Milman phenomenon, Urysohn metric spaces, and extremely amenable groups
• Competition interfaces and second class particles
• Random walks on quasirandom graphs
• On the concentration of eigenvalues of random symmetric matrices
• 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
• About the constants in Talagrand's concentration inequalities for empirical processes.
• Concentration of norms and eigenvalues of random matrices
• Interpolated inequalities between exponential and Gaussian, Orlicz hypercontractivity and isoperimetry
• Concentration for multidimensional diffusions and their boundary local times
• An approximate vertex-isoperimetric inequality for \(r\)-sets
• The missing log in large deviations for triangle counts
• On the geometry of similarity search: dimensionality curse and concentration of measure
• A Fourier view on the \(R\)-transform and related asymptotics of spherical integrals
• On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures
• Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
• A central limit theorem for the overlap in the Hopfield model
• Title not available (Why is that?)
• Concentration inequalities using the entropy method
• Noise sensitivity of Boolean functions and applications to percolation
• A direct verification argument for the Hamilton-Jacobi equation continuum limit of nondominated sorting
• Rigorous results for mean field models for spin glasses
• Around the circular law
• Detecting positive correlations in a multivariate sample
• Concentration for Poisson \(U\)-statistics: subgraph counts in random geometric graphs
• Error estimates and convergence rates for the stochastic homogenization of Hamilton-Jacobi equations
• Circular law theorem for random Markov matrices
• Merging percolation onZdand classical random graphs: Phase transition
• Randomly colouring graphs (a combinatorial view)
• Local tail bounds for functions of independent random variables
• A bound on the strong chromatic index of a graph
• Concentration of measure and spectra of random matrices: applications to correlation matrices, elliptical distributions and beyond
• A Stronger Bound for the Strong Chromatic Index
• An isoperimetric inequality for Gauss-like product measures
• A stochastic mechanism for signal propagation in the brain: force of rapid random fluctuations in membrane potentials of individual neurons
• A version of Hörmander's theorem for the fractional Brownian motion
• Concentration inequalities for dependent random variables via the martingale method
• Modified logarithmic Sobolev inequalities and transportation inequalities
• The concentration of measure phenomenon
• Concentration of Haar measures, with an application to random matrices
• Tyler's and Maronna's M-estimators: non-asymptotic concentration results
• Rate of convergence in first-passage percolation under low moments

   Recommendations

• A concentration inequality for product spaces 👍 👎
• An isoperimetric inequality for Gauss-like product measures 👍 👎
• On the isoperimetric constants for product measures 👍 👎
• Title not available (Why is that?) 👍 👎
• On measure concentration for separately Lipschitz functions in product spaces 👍 👎
• New concentration inequalities in product spaces 👍 👎
• Concentration of product spaces 👍 👎
• Title not available (Why is that?) 👍 👎
• On isoperimetric profiles of product spaces 👍 👎
• Poincare inequalities, isoperimetric estimates, and representation formulas on product spaces 👍 👎

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)