5.5 Martingale Concentration Inequalities

5.5.1 Martingale Concentration

Now we discuss martingale case. Recall that \(\{D_k\}_{k \geq 1}\) is a martingale difference sequence if \(\{\sum _{k=1}^n D_k\}_{n \geq 1}\) is a martingale with respect to \(\{\mathcal {F}_k\}_{k \geq 1}\).

This is a condition on how much the function changes if we change 1 coordinate. Here is a corollary of the Azuma-Hoeffding inequality.

5.5.2 Gaussian Complexity

Gaussian complexity is a very important notion in compressed sensing. Suppose we have a set \(A \subseteq \mathbb {R}^n\). How do we measure its “size”? A reasonable size function \(S\) should at least satisfy \(S(A) \leq S(B)\) if \(A \subseteq B\). Here are some reasonable size functions:

1.

Euclidean width: \(D(A) = \max _{a \in A} \|a\|_2\).

2.

Dimension: A line has dimension 1, and a plane has dimension 2.

Note that if we don’t take the supremum in the expectation, the quantity would be 0. This quantity is always nonnegative.

Note that if \(p_1 \leq p_2\), then \(q_1 \geq q_2\), so \(\mathcal {G}(B_{p_1}(r)) \leq \mathcal {G}(B_{p_2}(r))\).

We want to show that \(f(W) := \sup _{a \in A} \langle a, W \rangle \) concentrates. Fix \(w, w' \in \mathbb {R}^n\). Then \[ f(w) - f(w') = \sup _{a \in A} \langle a, w \rangle - \sup _{a \in A} \langle a, w' \rangle . \] Denote \(a^* = \arg \max _a \langle a, w \rangle \): \begin{align*} f(w) - f(w') &= \langle a^*, w \rangle - \sup _{a \in A} \langle a, w' \rangle \\ &= \inf _{a \in A} \langle a^*, w \rangle - \langle a, w' \rangle \\ &\leq \langle a^*, w - w' \rangle \\ &\leq \|a_*\| \|w - w'\|_2 \\ &\leq D(A) \|w - w'\|_2. \end{align*}

The other side can be proven similarly, so \(f\) is \(D(A)\)-Lipschitz. Concentration says that \(f(W)\) is \(\mathrm {sG}(D(A))\).