# Concentration Inequalities and Expected Suprema

Tags: :

A cheatsheet of some measure concentration results. Taken from:

- Philippe Rigollet’s High-Dimensional Statistics class notes.
- Gabor Lugosi’s Concentration of Measure Inequalities class notes.
- Vladimir Koltchinskii Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems, letcture notes.
- Larry Wasserman’s Concentration of Measure class notes.
- Shalev-Shwartz, Shai, and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. New York, NY: Cambridge University Press, 2014.

# Preliminaries

## Classes of Distributions

SubGaussian SubExponential

## Complexity Measures in Function Spaces

### Linear Dimension

### VC dimension

### Uniform Covering Numbers

### Random Covering Numbers

### Shattering Numbers

### Bracketing Numbers

### Bracketing Entropy

### Generic Chaining Complexities

# Conecntration Inequalities

## Of a Single Random Variable

## Of Sums of Random Variables

## Of Suprema of Stochastic Processes

### Markov’s Inequality

Polynomial decay ($t^{-1}$) of tail probability w.r.t. the expectation.

### Chebyshev’s inequality

Polynomial decay $t^{-2}$ of tail probability w.r.t. the variance.

### Generalized Chernoff bound

subExponenitial decay of tail probability of **sums**.

### Sums of subGaussian are subGaussian

### Gaussian Tail Inequality

Bounds the tail of a Gaussian w.r.t. its density (thus, a subGaussian inequality).

### Square of subGaussian

The **square** of a subGaussian (e.g. Chisq) is subExponential with related scale parameter.

### Hoffeding

subGaussian decay of tail probability of sums of **bounded support** random variables (garanteeing subGaussian tails).

### McDiarmid’s Inequality

A **bounded difference** function is subGaussian concentrated.

### Shawe-Taylor and Cristianini

Bound on the **sum of a bounded function** of some random variables.

### Bennet’s Inequality

Tighter than subGaussian decay of tails of sums.

### Sum of subExp is subExp

### Bernstein’s Inequality

subExp or subGausian tails for **sums** of subExponenital variables.

### Talagrand’s Inequality

A uniform version of Bernstein’s Inequality.

### Gine and Guillou Inequality

### Efron-Stein Inqeuality

A.k.a. *Influence Inequality*, *MG Bound on Variance*
Bound on the **variance** of an arbitrary function of random variables, w.r.t. the sum of the coordinate independent contributions.
Very powerful when compounding with Che

### Slud’s Inequality

A subGaussian **deconcentration** inequality for the Binomial distribution.
Put differently, the Binomial converges to a Gaussian, but has **heavier tails** all along the way.

### Maximal Inequality

- Over finite set
- Over convex polytope
- Over l_2 ball.

# Moment Bounds

The following bound the expectation, and not the tail probabilities.

## Non Negative subGaussian

The expectation of a non-negative subGaussian decays like $n^{-1/2}$.

## Expected Maximum over a Finite Set

The expectation of the max of subGaussians decays like $\sqrt{\log n}$.

## Expected Maximum with Covering Number

The expectation of the max of subGaussians decays like the integrated log of the covering number.