Concentration inequality

A concentration inequality bounds the probability that a random variable differs substantially from a typical value such as its expected value or median.

Chernoff bound

For every

λ > 0

, Markov inequality applied to

e^{λ X}

gives

P (X \geq t) \leq e^{- λ t} E [e^{λ X}] .

Optimizing over

λ

gives the Chernoff bound in terms of the moment-generating function of

X

.

Bounded differences property

f (x_{1}, \dots, x_{n})

has bounded differences with constants

c_{i}

when changing only

x_{i}

changes its value by at most

c_{i}

.

McDiarmid inequality

If

X_{1}, \dots, X_{n}

are independent random variables and

f

has bounded differences constants

c_{i}

, then

P (f (X) - E f (X) \geq t) \leq exp (- \frac{2 t ^{2}}{\sum _{i} c _{i}^{2}}),

and the same bound holds for the lower tail.

Certifiable function

An integer-valued function

f

is

g

-certifiable when every input

x

with

f (x) = k

has a set of at most

g (k)

coordinates whose values alone guarantee that

f \geq k

.

Talagrand concentration inequality for certifiable functions

Talagrand's product-space inequality gives sub-Gaussian-type concentration for a bounded-differences, certifiable function, with a variance scale controlled by the certificate size.

Entropy method for certifiable functions

The entropy method combines a coordinatewise certificate with tensorization of entropy to bound the moment-generating function of a certifiable random quantity and hence its tails.

Self-bounding function

A nonnegative function

f

of independent coordinates is self-bounding when there are coordinate-deleted versions

f_{i}

such that

0 \leq f - f_{i} \leq 1

and

\sum_{i} (f - f_{i}) \leq f .

These inequalities make the natural variance proxy no larger than the function itself.

Tensorization of entropy

For a nonnegative function

Z

of independent random variables, entropy is at most the sum of its conditional coordinate entropies. This tensorization is a basic step of the entropy method.

Transport-entropy inequality

A transport-entropy inequality controls an optimal expected transportation cost between probability distributions by their Kullback-Leibler divergence.

Tensorization of a transport-entropy inequality

If each coordinate law satisfies the same convex transport-entropy inequality, then the product law satisfies the sum-cost version. Sequentially couple conditional coordinates, apply Jensen inequality, and use the chain rule for relative entropy.

Sub-Poisson random variable in the right tail

A centered random variable

X

is sub-Poisson in the right tail with variance parameter

σ^{2}

when

lo g E e^{λ X} \leq σ^{2} (e^{λ} - λ - 1)

for every

λ \geq 0

.

Sub-Gamma random variable in the right tail

A centered random variable

X

is sub-Gamma in the right tail with variance parameter

v

and scale parameter

c

when

lo g E e^{λ X} \leq \frac{v λ ^{2}}{2 ( 1 - c λ )}

for

0 \leq λ < c^{- 1}

.

 Ancestors (6)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Concentration inequality by

Wikipedia Bot  1

Concentration inequalities are mathematical inequalities that provide bounds on how a random variable deviates from a certain value (typically its mean). These inequalities are essential in probability theory and statistics, particularly in the fields of machine learning, information theory, and statistical learning, because they help analyze the behavior of sums of random variables, as well as the performance of estimators and algorithms. There are several well-known concentration inequalities, each suitable for different types of random variables and different settings.

 Read the full article

  See all articles in the same topic Create my own version