Freedman's inequality for matrix martingales

An Introduction to Freedman’s Inequality

The Freedman inequality [Fre75, Thm. (1.6)] is a martingale extension of the Bernstein inequality. This result demonstrates that a martingale exhibits normal-type concentration near its mean value on a scale determined by the predictable quadratic variation, and the upper tail has Poisson-type decay on a scale determined by a uniform bound on the difference sequence.

Oliveira [Oli10, Thm. 1.2] proves that Freedman’s inequality extends, in a certain form, to the matrix setting. The purpose of this note is to demonstrate that the methods from the author’s paper [Tro10b] can be used to establish a sharper version of the matrix Freedman inequality. Furthermore, this approach offers a transparent way to obtain other probability inequalities for adapted sequences.

Let us introduce some notation and background on martingales so that we can state Freedman’s original result rigorously. Afterward, we continue with a statement of our main results and a presentation of the methods that we need to prove the matrix generalization.

For simplicity, we assume that the initial value of a martingale is null: $Y_{0}=0$. The difference sequence is the random process defined by

Roughly, the present value of a martingale depends only on the past values, and the martingale has the status quo property: today, on average, is the same as yesterday.

2. Freedman’s Inequality

Freedman uses a powerful stopping-time argument to establish the following theorem for scalar martingales [Fre75, Thm. (1.6)].

Consider a real-valued martingale $\{Y_{k}:k=0,1,2,\dots\}$ with difference sequence $\{X_{k}:k=1,2,3,\dots\}$. Assume that the difference sequence is uniformly bounded:

Define the predictable quadratic variation process of the martingale:

Then, for all $t\geq 0$ and $\sigma^{2}>0$,

When the difference sequence $\{X_{k}\}$ consists of independent random variables, the predictable quadratic variation is no longer random. In this case, Freedman’s inequality reduces to the usual Bernstein inequality [Lug09, Thm. 6].

3. Matrix Martingales

Matrix martingales are defined in much the same manner as scalar martingales. Consider a random process $\{\bm{Y}_{k}:k=0,1,2,\dots\}$ whose values are matrices of finite dimension. We say that the process is a matrix martingale when

We write $\left\|{\cdot}\right\|$ for the spectral norm, which coincides with the operator norm between Hilbert spaces. As before, we assume that $\bm{Y}_{0}=\bm{0}$, and we define the difference sequence $\{\bm{X}_{k}:k=1,2,3,\dots\}$ via the relation

A matrix-valued random process is a martingale if and only if we obtain a scalar martingale when we track each fixed coordinate in time.

4. Freedman’s Inequality for Matrices

In the elegant paper [Oli10], Oliveira establishes that it is possible to extend Freedman’s inequality to the matrix setting. He studies martingales that take self-adjoint matrix values, and he shows that the maximum eigenvalue of the martingale satisfies a result very similar to Freedman’s inequality. The uniform bound $R$ and the predictable quadratic variation $\{W_{k}\}$ are replaced by natural noncommutative extensions. As a consequence, these results have powerful applications in random matrix theory.

In this note, we establish a sharper version of Oliveira’s theorem [Oli10, Thm. 1.2].

Consider a matrix martingale $\{\bm{Y}_{k}:k=0,1,2,\dots\}$ whose values are self-adjoint matrices with dimension $d$, and let $\{\bm{X}_{k}:k=1,2,3,\dots\}$ be the difference sequence. Assume that the difference sequence is uniformly bounded in the sense that

Define the predictable quadratic variation process of the martingale:

Then, for all $t\geq 0$ and $\sigma^{2}>0$,

Here and elsewhere, $\lambda_{\max}$ denotes the algebraically largest eigenvalue of a self-adjoint matrix, and $\left\|{\cdot}\right\|$ denotes the spectral norm, which returns the largest singular value of a matrix.

Theorem 1.2 offers several concrete improvements over Oliveira’s original work. His theorem [Oli10, Thm. 1.2] requires a stronger uniform bound of the form $\left\|{\bm{X}_{k}}\right\|\leq R$, and the constants in his inequality are somewhat larger (but still very reasonable).

We prove Theorem 1.2 in Section 3 as a consequence of a stronger probability inequality that follows from a general result for adapted sequences of matrices. These tail bounds cannot be sharpened without changing their structure; see [Tro10b, §4 and §6] for a more detailed discussion.

As an immediate corollary of Theorem 1.2, we obtain a result for rectangular matrices.

Consider a matrix martingale $\{\bm{Y}_{k}:k=0,1,2,\dots\}$ whose values are matrices with dimension $d_{1}\times d_{2}$, and let $\{\bm{X}_{k}:k=1,2,3,\dots\}$ be the difference sequence. Assume that the difference sequence is uniformly bounded:

Define two predictable quadratic variation processes for this martingale:

Then, for all $t\geq 0$ and $\sigma^{2}>0$,

Define a self-adjoint matrix martingale $\{\bm{Z}_{k}\}$ with dimension $d=d_{1}+d_{2}$ via

Apply Theorem 1.2 to this martingale. See [Tro10b, §2.6 and §4.2] for some additional details about this type of argument. ∎

5. Tools and Techniques

In his paper [Oli10], Oliveira describes a way to transport Freedman’s stopping-time argument to the matrix setting. The main technical obstacle is to control the evolution of the moment generating function (mgf) of the matrix martingale. Oliveira accomplishes this task using an insightful variation on a idea due to Ahlswede and Winter [AW02, App.]. This method, however, does not result in the sharpest bounds on the matrix mgf.

This note demonstrates that the ideas from [Tro10b] allow us to obtain the sharp estimates for the mgf with minimal effort. Our main tool is a deep theorem [Lie73, Thm. 6] of Lieb.

Fix a self-adjoint matrix $\bm{H}$. The function

is concave on the positive-definite cone.

See [Tro10b, §3.3] and [Tro10a] for some additional discussion of this result. We apply Theorem 1.4 through the following simple corollary [Tro10b, Cor. 3.2]. We include a proof for completeness.

Let $\bm{H}$ be a fixed self-adjoint matrix, and let $\bm{X}$ be a random self-adjoint matrix. Then

The first identity follows because the logarithm can be defined as the functional inverse of the matrix exponential. Lieb’s result, Theorem 1.4, establishes that the trace function is concave in $\bm{Y}$, so we may invoke Jensen’s inequality to draw the expectation inside the logarithm. ∎

A significant advantage of our point of view is that the proof extends in a transparent way to yield other types of probability inequalities for adapted sequence of random matrices. We have dilated on this observation in a preliminary version of this work that is now available as a technical report [Tro11]. Here, for brevity, we focus on proving Freedman’s inequality.

Tail Bounds via Martingale Methods

In this section, we show that Freedman’s techniques extend to the matrix setting with minor (but profound) changes. The key idea is to use Corollary 1.5 to control the evolution of a matrix version of the moment generating function. This argument culminates in a rather general theorem on the large deviation behavior of an adapted sequence of random matrices. In §3, we specialize this result to obtain Freedman’s inequality.

In words, we can determine if the stopping time has arrived from current and past experience.

2. The Large Deviation Supermartingale

Consider an adapted random process $\{\bm{X}_{k}:k=1,2,3,\dots\}$ and a previsible random process $\{\bm{V}_{k}:k=1,2,3,\dots\}$ whose values are self-adjoing matrices with dimension $d$. Suppose that the two processes are connected through a relation of the form

where the function $g:(0,\infty)\to[0,\infty]$. The left-hand side should be interpreted as a conditional cumulant generating function (cgf); see [Tro10b, Sec. 3.1]. It is convenient to introduce the partial sums of the original process and the partial sums of the conditional cgf bounds:

The random matrix $\bm{W}_{k}$ can be viewed as a measure of the total variability of the process $\{\bm{X}_{k}\}$ up to time $k$. The partial sum $\bm{Y}_{k}$ is unlikely to be large unless $\bm{W}_{k}$ is also large.

To continue, we fix the function $g$ and a positive number $\theta$. Define a real-valued function with two self-adjoint matrix arguments:

We use the function $G_{\theta}$ to construct a real-valued random process.

This process is an evolving measure of the discrepancy between the partial sum process $\{\bm{Y}_{k}\}$ and the cumulant sum process $\{\bm{W}_{k}\}$. The following lemma describes the key properties of this random sequence. In particular, the average discrepancy decreases with time.

For each fixed $\theta>0$, the random process $\{S_{k}(\theta):k=0,1,2,\dots\}$ defined in (2.2) is a positive supermartingale whose initial value $S_{0}=d$.

It is easily seen that $S_{k}$ is positive because the exponential of a self-adjoint matrix is positive definite, and the trace of a positive-definite matrix is positive. We obtain the initial value from a short calculation:

To prove that the process is a supermartingale, we ascend a short chain of inequalities.

In the second line, we invoke Corollary 1.5, conditional on $\mathscr{F}_{k-1}$. This act is legal because $\bm{Y}_{k-1}$ and $\bm{W}_{k}$ are both measurable with respect to $\mathscr{F}_{k-1}$. The next inequality depends on the assumption (2.1) together with the fact that the trace exponential is monotone with respect to the semidefinite order [Pet94, §2.2]. The last step follows because $\{\bm{W}_{k}\}$ is the sequence of partial sums of $\{\bm{V}_{k}\}$. ∎

Finally, we present a simple inequality for the function $G_{\theta}$ that holds when we have control on the eigenvalues of its arguments.

Suppose that $\lambda_{\max}(\bm{Y})\geq t$ and that $\lambda_{\max}(\bm{W})\leq w$. For each $\theta>0$,

Recall that $g(\theta)\geq 0$. The bound results from a straightforward calculation:

The first inequality depends on the semidefinite relation $\bm{W}\preccurlyeq w\mathbf{I}$ and the monotonicity of the trace exponential with respect to the semidefinite order [Pet94, §2.2]. The second inequality relies on the fact that the trace of a psd matrix is at least as large as its maximum eigenvalue. The third identity follows from the spectral mapping theorem and elementary properties of the maximum eigenvalue map. ∎

3. A Tail Bound for Adapted Sequences

Our key theorem for adapted sequences provides a bound on the probability that the partial sum of a matrix-valued random process is large. In the next section, we apply this result to establish a stronger version of Theorem 1.2. This result also allows us to develop other types of probability inequalities for adapted sequences of random matrices; see the technical report [Tro11] for additional details.

Consider an adapted sequence $\{\bm{X}_{k}\}$ and a previsible sequence $\{\bm{V}_{k}\}$ of self-adjoint matrices with dimension $d$. Assume these sequences satisfy the relations

where the function $g:(0,\infty)\to[0,\infty]$. In particular, the hypothesis (2.3) holds when

To begin, note that the cgf hypothesis (2.3) holds in the presence of (2.4) because the logarithm is an operator monotone function [Bha97, Ch. V].

The overall proof strategy is identical with the stopping-time technique used by Freedman [Fre75]. Fix a positive parameter $\theta$, which we will optimize later. Following the discussion in §2.2, we introduce the random process $S_{k}:=G_{\theta}(\bm{Y}_{k},\bm{W}_{k})$. Lemma 2.1 implies that $\{S_{k}\}$ is a positive supermartingale with initial value $d$. These simple properties of the auxiliary random process distill all the essential information from the hypotheses of the theorem.

Define a stopping time $\kappa$ by finding the first time instant $k$ when the maximum eigenvalue of the partial sum process reaches the level $t$ even though the sum of cgf bounds has maximum eigenvalue no larger than $w$.

When the infimum is empty, the stopping time $\kappa=\infty$. Consider a system of exceptional events:

Construct the event $E:=\bigcup\nolimits_{k=0}^{\infty}E_{k}$ that one or more of these exceptional situations takes place. The intuition behind this definition is that the partial sum $\bm{Y}_{k}$ is typically not large unless the process $\{\bm{X}_{k}\}$ has varied substantially, a situation that the bound on $\bm{W}_{k}$ disallows. As a result, the event $E$ is rather unlikely.

We are prepared to estimate the probability of the exceptional event. First, note that $\kappa<\infty$ on the event $E$. Therefore, Lemma 2.2 provides a conditional lower bound for the process $\{S_{k}\}$ at the stopping time $\kappa$:

We require the fact that $S_{\kappa}$ is positive to justify these inequalities. Rearrange the relation to obtain

Minimize the right-hand side with respect to $\theta$ to complete the main part of the argument. ∎

Proof of Freedman’s Inequality

In this section, we use the general martingale deviation bound, Theorem 2.3, to prove a stronger version of Theorem 1.2.

Consider an adapted sequence $\{\bm{X}_{k}\}$ of self-adjoint matrices with dimension $d$ that satisfy the relations

Then, for all $t\geq 0$ and $\sigma^{2}>0$,

The function $h(u):=(1+u)\log(1+u)-u$ for $u\geq 0$.

Theorem 1.2 follows easily from this result.

To derive Theorem 1.2, we note that the difference sequence of $\{\bm{X}_{k}\}$ a matrix martingale $\{\bm{Y}_{k}\}$ satisfies the conditions of Theorem 3.1 and the martingale can be expressed using partial sums of the difference sequence. Finally, we apply the numerical inequality

which we obtain by comparing derivatives. ∎

We conclude with the proof of Theorem 3.1. The argument depends on the following estimate for the moment generating function of a zero-mean random matrix whose eigenvalues are uniformly bounded. See [Tro10b, Lem. 6.7] for the proof.

Suppose that $\bm{X}$ is a random self-adjoint matrix that satisfies

The main result follows quickly from this lemma.

We assume that $R=1$; the general result follows by re-scaling since $\bm{Y}_{k}$ is 1-homogeneous and $\bm{W}_{k}$ is 2-homogeneous. Invoke Lemma 3.2 conditionally to see that

The infimum is achieved when $\theta=\log(1+t/\sigma^{2})$. Finally, note that the norm of a positive-semidefinite matrix, such as $\bm{W}_{k}$, equals its largest eigenvalue. ∎

Acknowledgments

Roberto Oliveira introduced me to Freedman’s inequality and encouraged me to apply the methods from [Tro10b] to study the matrix extension of Freedman’s result. I would also like to thank Yao-Liang Yu, who pointed out an inconsistency in the proof of Theorem 2.3 and who proposed the argument in Lemma 3.2. Richard Chen and Alex Gittens have helped me root out (numerous) typographic errors.

References