In the mini-course to come, we will go through lots of concentration inequalities. There is a unite way to think about them which I will try to explain in this post.

Consider a sequence of i.i.d. random variables Consider their empirical mean

The interesting point about it is that for any (so, in a sense, the scaling is natural), but *concentrates* above its mean:

In fact, as we will see in the next post,

i.e. with exponentially high probability.

This is the simplest example of the **concentration of measure** phenomenon*,* when a function which is weakly dependent on many independent random variables concentrates around its mean or median. A collateral goal of the course is to observe similar properties in different settings: with broader classes of functions (Lipschitz functions, norms, quadratic forms, etc.), distributions of and mutual dependency in the sequence e.g. martingales.

### Like this:

Like Loading...

## About Dmitry Ostrovsky

PhD student with interests in learning theory, statistics, and optimization, working with Anatoli Juditsky and Zaid Harchaoui.

Pingback: Subgaussian distributions | Look at the corners!

Pingback: Subexponentials I: Bernstein inequality and deviations bound for a quadratic form | Look at the corners!