Subexponential distributions III — Johnson–Lindenstrauss lemma

In this post we will finish our affair with subexponential distributions. We will consider yet another example where they can be applied, an important statement called Johnson–Lindenstrauss lemma. Essentially, it states that  n  points in a high-dimensional Euclidean space may be projected in a subspace with dimension only  O(\log n)  such that all pairwise distances are well-preserved.

Continue reading

Posted in Course on Concentration Inequalities | Leave a comment

Subexponential distributions II — A closer look at Bernstein’s inequality

In the previous post we considered subexponential distributions and concentration inequality, called Berstein inequality, for independent sums of subexponential random variables. In this post we will concentrate more thoroughly on the meaning of parameters  (\sigma^2, b)  and the concept of  deviation zones.

Continue reading

Posted in Course on Concentration Inequalities | 1 Comment

Subexponential distributions I — Bernstein inequality and quadratic forms

In this post we move on from  subgaussian  distributions to another important class of distributions called  subexponential.  The simplest and most common example of such distributions is chi-square. As usual, we are interested in tail probability bounds for such distributions, and the way to obtain them will be Chernoff’s technique.

Continue reading

Posted in Course on Concentration Inequalities | 4 Comments

Chernoff bounding is good enough

There is a way to demonstrate that Chernoff bounding is — in some sense — optimal, and it relies to the so-called Sanov’s theorem, which controls the empirical distribution (as a random measure) in terms of the Kullback-Leibler divergence from the underlying measure.

Continue reading

Posted in Course on Concentration Inequalities | Tagged | Leave a comment

Subgaussian distributions

In this post we will discuss subgaussian distributions. In a nutshell, these are the ones that have as light tails as the Gaussian distribution.

Continue reading

Posted in Course on Concentration Inequalities | 2 Comments

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.

Continue reading

Posted in Course on Concentration Inequalities | 2 Comments

Mini-course on concentration inequalities

Recently I decided to start a ‘mini-course’ on concentration inequalities (possibly in parallel with the one on optimization). We’ll begin with some basic stuff that I’ve already familiar with (subgaussians, subexponentials, Bernstein, McDiarmid, martingales, Orlicz norms); then the plan is to move on to some a bit more advanced topics with some good lecture notes at hand.

Posted in Course on Concentration Inequalities | Leave a comment