Intuition behind concentration inequalities

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  X_i \sim \mathcal{N}(\mu, \sigma^2),  i = \overline{1, n}.  Consider their empirical mean

\displaystyle F(X_1,\, \dotsc,\, X_n) = \frac{1}{n}\sum_{i = 1}^n X_i.

The interesting point about it is that for any  n,  \mathbf{E} F(X_1,\, \dotsc,\, X_n) = \mu  (so, in a sense, the scaling \frac{1}{n} is natural), but F(X_1,\, \dotsc,\, X_n)  concentrates above its mean:

\displaystyle \text{Var}\, F(X_1,\, \dotsc,\, X_n) \le \frac{\sigma^2}{n}

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

\displaystyle P\left(F(X_1,\, \dotsc,\, X_n) - \mu \ge x \right) \le \exp\left(-\frac{n x}{2\sigma^2}\right),

i.e.  \displaystyle F(X_1,\, \dotsc,\, X_n) - \mu \le \sigma^2/n  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  F  (Lipschitz functions, norms, quadratic forms, etc.), distributions of  X_i,  and mutual dependency in the sequence  (X_1,\, \dotsc,\, X_n),  e.g. martingales.


About Dmitry Ostrovsky

PhD student with interests in learning theory, statistics, and optimization, working with Anatoli Juditsky and Zaid Harchaoui.
This entry was posted in Course on Concentration Inequalities. Bookmark the permalink.

2 Responses to Intuition behind concentration inequalities

  1. Pingback: Subgaussian distributions | Look at the corners!

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s