maximal inequalities

To motivate maximal inequalities, I’ll quote from the opening of Michel Talagrand’s excellent book Upper and Lower Bounds for Stochastic Processes:

What is the maximum level a certain river is likely to reach over the next 25 years? What is the likely magnitude of the strongest earthquake to occur during the life of a planned nuclear plant, or the speed of the strongest wind a suspension bridge will have to stand? The present book does not deal with such fundamental practical questions, but rather with some (arguably also fundamental) mathematics which have emerged from the consideration of these questions. All these situations can be modeled in the same manner. The value $X_t$ of the quantity of interest (be it water level or speed of wind) at time $t$ is a random variable. What can be said about the maximum value of $X_t$ over a certain range of $t$? In particular, how can we guarantee that, with probability close to one, this maximum will not exceed a given threshold?

Mathematically, maximal inequalities are concerned with suprema of a stochastic process $(X_{\theta }{)}_{\theta \in \Theta }$ where $\Theta$ is an index set in some space—often in ${\mathbb{R}}^d$ be could be a Hilbert space or a Banach space. That is, we usually want to bound

$$\mathbb{E}\underset{\theta \in \Theta }{\sup }|X_{\theta }|,\text{or}\mathbb{P}(\underset{\theta }{\sup }|X_{\theta }|\ge B).$$

Often $\Theta$ is equipped with a metric $d$ and we consider the metric space $(\Theta ,d)$. $\Theta$ could be time (i.e., ${\mathbb{R}}_{\ge 0}$ or $\mathbb{N}$), but is usually not. These objectives are usually pursued simultaneously, since

$$\mathbb{E}\underset{\theta }{\sup }|X_{\theta }|={\int }_0^{\infty }\mathbb{P}(\underset{\theta }{\sup }|X_{\theta }|\ge t)\text{d}t,$$

so a bound on the latter provides a bound on the former. $X_{\theta }$ is usually assumed to be centered (zero-mean) and often symmetric, so that we can instead work with $|X_{\theta }-X_{\varphi }|$ instead of $|X_{\theta }|$ (since, under this assumption, $\mathbb{E}{\sup }_{\theta ,\varphi }|X_{\theta }-X_{\varphi }|=2\mathbb{E}{\sup }_{\theta }{X}_{\theta }$). See, e.g., generic chaining, which makes this assumption.

Both Gaussian complexity and Rademacher complexity are defined as maximal inequalities.

Maximal inequalities can be used to obtain concentration inequalities. If $(S_t)$ is some process, then $\left|S_t\right|={\sup }_{\theta }⟨\theta ,S_t⟩$, and maximal inequalities help bound the latter quantity. See techniques for multivariate concentration.

References

• Wainwright’s High dimensional statistics: A nonasymptotic viewpoint, Chapter 5.
• Talagrand’s Upper and Lower Bounds for Stochastic Processes, Chapter 2.