concentration inequalities

For a random variable $X$ taking values in some normed space $(\mathcal{X},\Vert \cdot \Vert )$, concentration is the search for decreasing functions $f(u)$ such that

$$P(\Vert X-Z\Vert \ge u)\le f(u),$$

where $Z\in \mathcal{X}$ is some point of interest (often $Z=\mathbb{E}X$). This page is a high-level pointer to more specific concentration inequalities in various settings. For specific results, see:

• bounded scalar concentration
• light-tailed, unbounded scalar concentration
• heavy-tailed concentration
• martingale concentration
• multivariate concentration
• cdf concentration
• concentration in Banach spaces
• matrix inequalities
• concentration of functions

For notes related to techniques to achieve concentration, see:

• techniques for multivariate concentration
• exponential inequalities, which typically underlie the proofs of many concentration inequalities, and
• basic inequalities, which contains the building blocks for many concentration results (eg Markov’s inequality and the Chernoff method).

A few other things:

• Anti-concentration inequalities, which are exactly what they sound like.
• A 1998 result of Montgomery-Smith and Pruss which allows one to go from independence to iid in general Banach spaces.
• In light-tailed settings, concentration is often synonymous with mean estimation, whereas this is not the case in heavy-tailed settings. See mean estimation for more.