Concentration of Martingale Difference Sequences

We have so far reviewed concentration results for sub-Gaussian and sub-exponential random variables. Much of what we studied concerned sums of independent random variables: For example, we showed that the sum of independent sub-Gaussian random variables is itself a sub-Gaussian random variable, and used those results to derive inequalities.

In this post, we’ll take a look at the more general notion of stochastic processes and, in particular, a special stochastic process called martingale. This method helps us derive concentration bounds for certain functions of independent random variables - not just their sums. First, though, let’s review some of the basics.

Martingales

Consider a sequence of $\sigma$-algebras $\{ \mathcal{F}_n \}$ such that $\mathcal{F}_i \subseteq \mathcal{F}_{i+1}$; that’s called a filtration. A sequence of random variables $\{ X_n \}_{n \geq 0}$ is a martingale if:

• $X_n$ is adapted to the filtration (i.e., $X_n$ is $\mathcal{F}_n$-measurable, so that $\mathbb{E}[X_n \;\lvert\; \mathcal{F}_n]=X_n$);
• $\mathbb{E}\big[\lvert X_n \rvert \big]$ exists; and,
• $\mathbb{E}[X_n \;|\; \mathcal{F}_{n-1}] = X_{n-1}$ almost surely.

It’s easy to verify that the partial sum of independent zero-mean random variables is a martingale. That is, given a sequence of random variables $\{ X_i \}_{i=1}^n$ with mean zero, $S_k=\sum_{i=1}^k X_i$ for $k \in [n]$ is a martingale with respect to the $\sigma$-algebra generated by $X_i$’s. So is the product of random variables with mean $1$: $P_k=\prod_{i=1}^k X_i$.

The Doob martingale is another example, which is constructed as follows: Say we have a function $f:\mathbb{R}^n \rightarrow \mathbb{R}$ and a sequence of $n$ random variables $\{ X_i \}_{i=1}^n$. If we define $Y_k=\mathbb{E}\big[ f(X) \;|\; \{ X_i \}_{i=1}^{k} \big]$ (or, more precisely, conditioning on the $\sigma$-algebra generated by the first $k$ random variables), and let $Y_0=\mathbb{E}[f(X)]$ and $Y_n=f(X)$, then the sequence $\{ Y_k \}_{k=1}^n$ is a martingale if $\mathbb{E}[\lvert f(X) \rvert]$ exists.

A related notion is the martingale difference sequence: If a sequence $\{ \Delta_i \}_{i\geq 1}$ with respect to a filtration $\{ \mathcal{F}_i \}_{i \geq 1}$ has the property that $\mathbb{E}[\lvert \Delta_k \rvert]$ is finite and that $\mathbb{E}[\Delta_k \;|\; \mathcal{F}_{k-1}]=0$, then it is a martingale difference sequence. For example, when $\{ X_i \}_{i\geq 0}$ is a martingale with respect to some filtration $\{ \mathcal{F}_i\}_{i \geq 0}$, then $\{ \Delta_i \}_{i \geq 1}$ where $\Delta_i=X_i-X_{i-1}$ is a difference sequence.

Tail Bounds for Sub-Exponential Martingale Difference Sequences

Let’s take a martingale difference sequence, $\{ \Delta_i \}_{i \geq 1}$ with flitration $\{ \mathcal{F}_i \}_{i \geq 1}$, and impose the following constraint on it:

$\mathbb{E}\Big[ e^{\lambda \Delta_k} \;|\; \mathcal{F_{k-1}}\Big] \leq e^{\lambda^2 \nu_k^2/2}, \quad \forall \; \lvert \lambda \rvert \leq \frac{1}{\alpha_k}.$

In other words, we require that $\Delta_k$ is sub-exponential with parameters $(\nu_k, \alpha_k)$ for all $k$. Then it’s not hard to see the following result:

As a result, we can apply tail bounds for sub-exponential random variables to the random variable $\sum_{i=1}^n \Delta_i$. For example:

$\mathbb{P}\Big[ \big\lvert \sum_{i=1}^n \Delta_i \big\rvert \geq t \Big] \leq \begin{cases} 2\exp\big( -\frac{t^2}{2\sum_{i=1}^n \nu_i^2} \big) & 0 \leq t \leq \frac{\sum_{i=1}^n \nu_i^2}{\max_{i \in [n]} \alpha_i };\\ 2\exp\big( -\frac{t^2}{2 \max_{i \in [n]} \alpha_i} \big) & t > \frac{\sum_{i=1}^n \nu_i^2}{\max_{i \in [n]} \alpha_i } \end{cases}.$

As a direct consequence of this result, it is again straightforward to see that, if a martingale difference sequence is bounded, it is sub-exponential, and as such bounds such as Hoeffding’s inequality hold:

Concentration of Functions with Bounded Difference Property

Sub-exponential martingale difference sequences are super useful! Well, really, the fact that bounded random variables are sub-Gaussian is a helpful result that, combined with martingale difference sequences allows us to apply tail bounds to stochastic processes.

Martingales aren’t limited to sums of independent random varaibles, however. So it is natural to ask if we can extend concentration results to a more general construction such as the Doob martingale. Why is such a generalization useful? To answer that, let’s have a look at one important example.

Suppose we have a function $f:\mathbb{R}^n \rightarrow \mathbb{R}$ and we are interested in understanding the concentration of $f(X)$ around its mean, $\mathbb{E}[f(X)]$. Now, what does the Doob martingale look like? Well, $Y_0=\mathbb{E}[f(X)]$, $Y_n=f(X)$, and $Y_k=\mathbb{E}[f(X) \;|\; \{ X_i \}_{i=1}^k]$. But we can write:

$f(X)-\mathbb{E}[f(X)] = Y_n - Y_0 = \sum_{k=1}^n (Y_k - Y_{k-1}).$

The right-hand side is the sum of martingale differences! So indeed we may be able to impose some conditions on the function $f(\cdot)$ and use our results from the previous section to bound the deviation of $f(X)$ from its mean. The following result does exactly that:

Let’s illustrate the result by applying it to a rather ubiquitous random variable: If $\mathcal{X} \subset \mathbb{R}^n$ is a vector collection, then:

$\mathcal{R}(\mathcal{X}) := \mathbb{E}_\xi \big[\sup_{u \in \mathcal{X}} \langle u, \xi \rangle \big],$

where $\xi \in \{-1, 1\}^n$ is a random Rademacher vector, is called the Rademacher complexity of the set $\mathcal{X}$. Now consider the random variable $Z=\sup_{u \in \mathcal{X}} \langle u, \xi \rangle$ and notice that it is bounded in the sense of the previous theorem:

$\sup_{\xi, \xi^{\setminus k}} \lvert Z - Z^{\setminus k} \rvert = \sup_{\xi, \xi^{\setminus k}} \lvert \sup_{u \in \mathcal{X}} \langle u, \xi - \xi^{\setminus k} \rangle \rvert = \sup_{u \in \mathcal{X}} \lvert u_k (\xi_k - \xi^{\setminus k}_k) \rvert \leq 2\sup_{u \in \mathcal{X}} \lvert u_k \rvert.$

As a result:

$\mathbb{P}\Big[ \lvert Z - \mathcal{R}(\mathcal{X}) \rvert \geq t \Big] \leq 2\exp(-\frac{2t^2}{\alpha^2}),$

where $\alpha^2=4\sum_{i=1}^n \sup_{u \in \mathcal{X}} u_k^2$.