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

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

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?)
• Probability Inequalities for Sums of Bounded Random Variables
• New concentration inequalities in product spaces
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• A matching problem and subadditive Euclidean functionals
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exponential Bounds for Large Deviations
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)

• 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
• Concentration for independent random variables with heavy tails
• Rate of convergence in first-passage percolation under low moments
• Exponential concentration for first passage percolation through modified Poincaré inequalities
• Central limit theorem for first-passage percolation time across thin cylinders
• Random-weighted Sobolev inequalities on \(\mathbb{R}^d\) and application to Hermite functions
• Random assignment problems
• Exponential integrability and transportation cost related to logarithmic Sobolev inequalities
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• A stronger bound for the strong chromatic index (extended abstract)
• On amenability and groups of measurable maps
• Moment inequalities for functions of independent random variables
• Complexity measures of sign matrices
• The infamous upper tail
• On the geometry of metric measure spaces. I
• The adjacent vertex distinguishing total chromatic number
• Sublinear variance in first-passage percolation for general distributions
• On the uniform convergence of empirical norms and inner products, with application to causal inference
• A concentration inequality for product spaces
• Connected spatial networks over random points and a route-length statistic
• Spectrum of non-Hermitian heavy tailed random matrices
• Bounding \(\bar d\)-distance by informational divergence: A method to prove measure concentration
• On the concentration and the convergence rate with a moment condition in first passage percolation
• Random weighting, asymptotic counting, and inverse isoperimetry
• Limit theory for the Gilbert graph
• Symmetric Langevin spin glass dynamics
• On Hoeffding's inequalities.
• Signal propagation in small-world biological networks with weak noise
• On concentration for (regularized) empirical risk minimization
• A new look at independence
• Transportation cost for Gaussian and other product measures
• A Hsu-Robbins-Erdős strong law in first-passage percolation
• Empirical risk minimization is optimal for the convex aggregation problem
• Concentration inequalities for functions of independent variables
• The sub-Gaussian constant and concentration inequalities
• Applications of Stein's method for concentration inequalities
• Singular perturbations to semilinear stochastic heat equations
• Title not available (Why is that?)
• Concentration inequalities and limit theorems for randomized sums
• Constructive bounds for a Ramsey-type problem
• Variational bounds for the generalized random energy model
• A measure concentration inequality for contracting Markov chains
• Theory of Classification: a Survey of Some Recent Advances
• Nonlinear large deviations
• Generalization error rates in kernel regression: the crossover from the noiseless to noisy regime*
• Phase transitions in normalized cut of social networks
• Fisher information and logarithmic Sobolev inequality for matrix-valued functions
• Applications of weak transport theory
• The planted matching problem: phase transitions and exact results
• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Stability of martingale optimal transport and weak optimal transport
• Talagrand's inductive method and isoperimetric inequalities involving random sets

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)