Misplaced Pages

Talagrand's concentration inequality

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Isoperimetric-type inequality on product spaces
This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (January 2022) (Learn how and when to remove this message)

In the probability theory field of mathematics, Talagrand's concentration inequality is an isoperimetric-type inequality for product probability spaces. It was first proved by the French mathematician Michel Talagrand. The inequality is one of the manifestations of the concentration of measure phenomenon.

Roughly, the product of the probability to be in some subset of a product space (e.g. to be in one of some collection of states described by a vector) multiplied by the probability to be outside of a neighbourhood of that subspace at least a distance t {\displaystyle t} away, is bounded from above by the exponential factor e − t 2 / 4 {\displaystyle e^{-t^{2}/4}} . It becomes rapidly more unlikely to be outside of a larger neighbourhood of a region in a product space, implying a highly concentrated probability density for states described by independent variables, generically. The inequality can be used to streamline optimisation protocols by sampling a limited subset of the full distribution and being able to bound the probability to find a value far from the average of the samples.

Statement

The inequality states that if Ω = Ω 1 × Ω 2 × ⋯ × Ω n {\displaystyle \Omega =\Omega _{1}\times \Omega _{2}\times \cdots \times \Omega _{n}} is a product space endowed with a product probability measure and A {\displaystyle A} is a subset in this space, then for any t ≥ 0 {\displaystyle t\geq 0}

Pr [ A ] ⋅ Pr [ A t c ] ≤ e − t 2 / 4 , {\displaystyle \Pr\cdot \Pr \left\leq e^{-t^{2}/4}\,,}

where A t c {\displaystyle {A_{t}^{c}}} is the complement of A t {\displaystyle A_{t}} where this is defined by

A t = { x ∈ Ω :   ρ ( A , x ) ≤ t } {\displaystyle A_{t}=\{x\in \Omega \colon ~\rho (A,x)\leq t\}}

and where ρ {\displaystyle \rho } is Talagrand's convex distance defined as

ρ ( A , x ) = max α , ‖ α ‖ 2 ≤ 1   min y ∈ A   ∑ i :   x i ≠ y i α i {\displaystyle \rho (A,x)=\max _{\alpha ,\|\alpha \|_{2}\leq 1}\ \min _{y\in A}\ \sum _{i\colon ~x_{i}\neq y_{i}}\alpha _{i}}

where α ∈ R n {\displaystyle \alpha \in \mathbf {R} ^{n}} , x , y ∈ Ω {\displaystyle x,y\in \Omega } are n {\displaystyle n} -dimensional vectors with entries α i , x i , y i {\displaystyle \alpha _{i},x_{i},y_{i}} respectively and ‖ ⋅ ‖ 2 {\displaystyle \|\cdot \|_{2}} is the ℓ 2 {\displaystyle \ell ^{2}} -norm. That is,

‖ α ‖ 2 = ( ∑ i α i 2 ) 1 / 2 {\displaystyle \|\alpha \|_{2}=\left(\sum _{i}\alpha _{i}^{2}\right)^{1/2}}

References

  1. Alon, Noga; Spencer, Joel H. (2000). The Probabilistic Method (2nd ed.). John Wiley & Sons, Inc. ISBN 0-471-37046-0.
  2. ^ Ledoux, Michel (2001). The Concentration of Measure Phenomenon. American Mathematical Society. ISBN 0-8218-2864-9.
  3. Talagrand, Michel (1995). "Concentration of measure and isoperimetric inequalities in product spaces". Publications Mathématiques de l'IHÉS. 81. Springer-Verlag: 73–205. arXiv:math/9406212. doi:10.1007/BF02699376. ISSN 0073-8301. S2CID 119668709.
  4. Castelvecchi, Davide (21 March 2024). "Mathematician who tamed randomness wins Abel Prize". Nature. doi:10.1038/d41586-024-00839-6.


Stub icon

This probability-related article is a stub. You can help Misplaced Pages by expanding it.

Categories: