Concentration of Martingale Difference Sequences

Sub-exponentialness is such an important property, as we saw in earlier posts. We learnt, for example, that sums of independent sub-exponential random variables are themselves sub-exponential random variables, allowing us to extend concentration results to sums. In this post, I'll review another important result that allows us to apply the same results (such as Hoeffding's inequality) to functions of independent random variables, under certain conditions.

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.

Proof: We have to show that the sequence $\{ Y_k \}$ has the properties of a martingale. First, notice that:

$\mathbb{E} \Big[ \lvert Y_k \rvert \Big] = \mathbb{E} \Big[ \lvert \mathbb{E}\big[ f(X) \;|\; \{ X_i \}_{i=1}^k \big] \rvert \Big] \leq \mathbb{E} \Big[ \mathbb{E}\big[ \lvert f(X) \rvert \;|\; \{ X_i \}_{i=1}^k \big] \Big]= \mathbb{E}\Big[ \lvert f(X) \rvert \Big],$

which exists by assumption. As for the second property:

$\mathbb{E}\Big[ Y_{k+1} \;|\; \{X_i\}_{i=1}^k \Big] = \mathbb{E}\Big[ \mathbb{E}\big[ f(X) \;|\; \{ X_i\}_{i=1}^{k+1} \big] \;|\; \{X_i\}_{i=1}^k \Big] =\mathbb{E}\Big[ f(X) \;|\; \{X_i\}_{i=1}^{k} \Big] = Y_k.$

The Doob martingale updates the conditional prediction of f(X) as inputs are revealed. Its increments need not be independent: conditioning on the revealed past is what gives each increment mean zero. View largerScroll sideways for the full sketch.

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.

Proof: The first property is trivial to show. As for the second property:

$\mathbb{E}\Big[\Delta_{k+1} \;|\; \mathcal{F}_k \Big] = \mathbb{E}\Big[ X_{k+1} - X_k \;|\; \mathcal{F}_k \Big] = \mathbb{E}\Big[ X_{k+1} \;|\; \mathcal{F}_k \Big] - X_k = X_k-X_k=0.$

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:

Any partial sum of the sub-exponential martingale differences, $\sum_{i=1}^n \Delta_i$ , with parameters $(\nu_k, \alpha_k)$ for all $k$ , is itself a sub-exponential random variable.

Proof: Let’s start with the definition of a sub-exponential random variable:

$\mathbb{E}\Big[ e^{\lambda \sum_{i=1}^n \Delta_i} \Big] = \mathbb{E}\Big[ e^{\lambda \sum_{i=1}^{n-1} \Delta_i} \mathbb{E}\big[ e^{\lambda \Delta_n} \;|\; \mathcal{F}_{n-1} \big] \Big] \leq \mathbb{E}\Big[ e^{\lambda \sum_{i=1}^{n-1} \Delta_i} \Big] e^{\lambda^2 \nu_n^2/2}.$

Continuing with this process iteratively, we find that the partial sum is indeed sub-exponential with parameters $\Big( \sqrt{\sum_{i=1}^n \nu_i^2},\; \max_{i \in [n]} \alpha_i \Big)$ .

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:

If $\{ \Delta_i \}_{i \geq 1}$ is a martingale difference sequence with filtration $\{ \mathcal{F}_i \}_{i \geq 1}$ with the property that $\Delta_i \in [a_i, b_i]$ almost surely for all $i$ , then:

$\mathbb{P}\Big[ \big\lvert \sum_{i=1}^n \Delta_i \big\rvert \geq t \Big] \leq 2e^{-2t^2/\sum_{i=1}^n (b_i - a_i)^2}.$

Proof: Because $\Delta_i \in [a_i, b_i]$ is bounded, it is sub-Gaussian with constant $\sigma_i=(b_i - a_i)/2$ as shown here. This tells us that:

$\mathbb{E}\Big[ e^{\lambda \Delta_i} \;|\; \mathcal{F}_{i-1} \Big] \leq e^{\lambda^2 (b_i - a_i)^2/8}.$

As a result, the sum of $\Delta_i$ ’s is sub-Gaussian with constant $\sqrt{\sum_{i=1}^n (b_i - a_i)^2}/2$ , so that we may apply Hoeffding’s inequality and obtain the result above.

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:

McDiarmid’s Inequality: Suppose $f$ has the property that $\lvert f(x) - f(x^{\setminus k}) \rvert \leq \alpha_k$ where $x^{\setminus k}$ denotes a copy of the vector $x$ that differs from $x$ in the $k$ -th dimension only. In other words, changing the $k$ -th coordinate of the input changes the output of $f$ by at most $\alpha_k$ . If the random vector $X$ has independent components, then:

$\mathbb{P}\Big[ \big\lvert f(X) - \mathbb{E}[f(X)] \big\rvert \geq t \Big] \leq 2 \exp(- \frac{2t^2}{\sum_{i=1}^n \alpha_i^2}).$

With independent input coordinates, hold all but coordinate k fixed. If f can change by at most αₖ, then, after conditioning on the past, the possible values of Δₖ lie in an interval of width at most αₖ. This is the bridge to the bounded-increment tail bound. View largerScroll sideways for the full sketch.

Proof: We have already seen that $f(X) - \mathbb{E}[f(X)]$ can be expressed as the sum of a martingale difference sequence. If we showed that $\Delta_k=Y_k - Y_{k-1}$ belongs to an interval of length at most $\alpha_k$ , then we can apply Hoeffding’s inequality to obtain the desired result. So we’ll focus on bounding $\Delta_k$ ’s.

By definition, we have that:

$\Delta_k=\mathbb{E}\Big[ f(X) \;|\; \{X_i\}_{i=1}^k \Big] - \mathbb{E}\Big[ f(X) \;|\; \{X_i\}_{i=1}^{k-1} \Big].$

Now define the following random variables:

$U_k=\sup_{x \in \mathbb{R}} \mathbb{E}\Big[ f(X) \;|\; \{X\}_{i \leq k-1}, x \Big]- \mathbb{E}\Big[ f(X) \;|\; \{X\}_{i \leq k-1} \Big],$

and,

$L_k=\inf_{x \in \mathbb{R}} \mathbb{E}\Big[ f(X) \;|\; \{X\}_{i \leq k-1}, x \Big]- \mathbb{E}\Big[ f(X) \;|\; \{X\}_{i \leq k-1} \Big].$

Notice that $L_k \leq \Delta_k \leq U_k$ . But now:

$\begin{aligned} U_k - L_k &= \sup_{x \in \mathbb{R}} \mathbb{E}\Big[ f(X) \;|\; \{X\}_{i \leq k-1}, x \Big]- \inf_{x \in \mathbb{R}} \mathbb{E}\Big[ f(X) \;|\; \{X\}_{i \leq k-1}, x \Big] \\ &\leq \sup_{x,y \in \mathbb{R}} \mathbb{E}\Big[ f(X) \;|\; \{X\}_{i \leq k-1}, x \Big]- \mathbb{E}\Big[ f(X) \;|\; \{X\}_{i \leq k-1}, y \Big] \\ &= \sup_{x,y \in \mathbb{R}} \mathbb{E}_{\{X_i\}_{i \geq k+1}}\Big[ f(\{X_i\}_{i \leq k-1}, x, \{X_i\}_{i \geq k+1}) \Big] \\ &\quad\quad- \mathbb{E}_{\{X_i\}_{i \geq k+1}}\Big[ f(\{X_i\}_{i \leq k-1}, y, \{X_i\}_{i \geq k+1}) \Big] \leq \alpha_k, \end{aligned}$

where we used the fact that $\mathbb{E}[f(X) \;|\; \{x_i\}_{i \leq k}] = \mathbb{E}_{\{X_i\}_{i \geq k+1}}[f(x_1, x_2, \ldots, x_k, X_{k+1}, \ldots, X_n)]$ .

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$ .