# 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

# Conecntration Inequalities

## 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.

### 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.

### Bernstein’s Inequality

subExp or subGausian tails for sums of subExponenital variables.

### Talagrand’s Inequality

A uniform version of Bernstein’s 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.

Written on