1 Bernstein concentration inequality

The standard Bernstein inequality for real random variables demonstrates that a sum of independent bounded random variables exhibits normal concentration near its mean on a scale determined by the variance of the sum.

Theorem 1 (Bernstein inequality).

Let $\{S_1,\mathrm{\dots },S_n\}$ be independent and centered real random variables satisfying $|S_i|\le R$ a.s. for $i=1,\mathrm{\dots },n$. Let $Z={\sum }_{i=1}^n{S}_i$ and assume $𝔼[Z^2]={\sum }_{i=1}^n𝔼[S_i^2]\le {\sigma }^2$. Then for any $t>0$,

$\mathbb{P}(|Z|\ge t)\le \exp \left({\displaystyle \frac{-t^2/2}{{\sigma }^2+Rt/3}}\right).$

Sums of independent random matrices exhibit the same type of behavior, where the normal concentration depends on a matrix generalization of the variance and the tails are controlled by a uniform bound on the spectral norm of each summand [3].

Theorem 2 (Matrix Bernstein concentration).

Let $\{S_1,\mathrm{\dots },S_n\}$ be independent random real symmetric matrices with dimension $d$. Assume each random matrix satisfies

$$𝔼[S_i]=\mathrm{𝟎}\mathrm{and}\Vert S_i\Vert \le R\mathrm{a}.\mathrm{s}.$$

where $\parallel \cdot \parallel$ is the matrix spectral norm, and $\Vert {\sum }_{i=1}^n𝔼[S_i^2]\Vert \le {\sigma }^2$. Then for any $t>0$,

$\mathbb{P}(\Vert Z\Vert \ge t)\le d\cdot \exp \left({\displaystyle \frac{-t^2/2}{{\sigma }^2+Rt/3}}\right).$ (1)

A remarkable feature is that the above bound depends on the dimension of the matrices. On the other hand, in [2, Chapter 7], Tropp points out that $d$ can be replaced by the so called “intrinsic dimension” of a matrix.

2 Operator Bernstein concentration

For a positive-semidefinite Hilbert-Schmidt operator $A$, we can also define the intrinsic dimension of it, as $r(A)=\frac{\mathrm{Tr}(A)}{\Vert A\Vert }$ (if $A$ is also trace class). The following result is from [1].

Theorem 3 (Operator Bernstein concentration).

Let $\{S_1,\mathrm{\dots },S_n\}$ be independent random self-adjoint Hilbert–Schmidt operators, where $S_i:H\to H$ acts on a separable Hilbert space $H$. Assume each random operator satisfies

$$𝔼[S_i]=\mathrm{𝟎}\mathrm{and}\Vert S_i\Vert \le R\mathrm{a}.\mathrm{s}.$$

where $\parallel \cdot \parallel$ is the operator norm, and $\Vert {\sum }_{i=1}^n𝔼[S_i^2]\Vert \le {\sigma }^2$. Then for any $t\ge \frac{1}{6}(R+{(R^2+36{\sigma }^2)}^{1/2})$,

$\mathbb{P}(\Vert Z\Vert \ge t)\le r({\displaystyle \sum _{i=1}^n}𝔼[S_i^2])\cdot \exp \left({\displaystyle \frac{-t^2/2}{{\sigma }^2+Rt/3}}\right).$ (2)

In statistical learning, random self-adjoint operators frequently emerge in the study of approximation errors. Assume $x$ be a random data in $X$. Rigorously speaking, let $(\mathrm{\Omega },𝒜,\mathbb{P})$ be a probability space and $x:(\mathrm{\Omega },𝒜)\to (X,ℱ)$ be measurable, such that the distribution on $X$ is $\nu =\mathbb{P}\circ x^{-1}$. Let $K(\cdot ,\cdot ):X\times X\to ℝ$ be a symmetric positive definite kernel, satisfying . Define the kernel integral operator $T$ on $L^2(X,ℱ,\nu )$ be

$(Tf)(x)={\displaystyle {\int }_X}K(x,y)f(y)\nu (\mathrm{d}y).$ (3)

Then $T$ is a Hilbert–Schmidt operator with the Hilbert–Schmidt norm satisfying

${\Vert T\Vert }_{\mathrm{HS}}^2={\displaystyle {\int }_{X\times X}}{|K(x,y)|}^2(\nu \otimes \nu )(\mathrm{d}(x,y))\le {\kappa }^2,$

where we have used $K{(x,y)}^2\le K(x,x)K(y,y)$.

Let $\mathscr{H}$ be the Reproducing Kernel Hilbert Space (RKHS) with kernel $K$. If $X$ is a locally compact Hausdorff space, $\nu$ a $\sigma$-finite Radon measure, and $K\in L^2(X,\nu )$, then $\mathscr{H}$ is separable. In fact, the collection of countable eigenfunctions of $T$ corresponding to positive eigenvalues forms a complete orthogonal basis.

Suppose we have $n$ i.i.d. samples of $x$, i.e., $\{x_1,\mathrm{\dots },x_n\}$ are i.i.d. random variables with the same distribution as $x$. Define the empirical operator on $\mathscr{H}$ as

$T_n={\displaystyle \frac{1}{n}}{\displaystyle \sum _{i=1}^n}{K}_{x_i}\otimes K_{x_i}.$ (4)

Now $T_i$ is a random self-adjoint operator, and it will approximate $T$ as $n\to \mathrm{\infty }$. Notice that $T$ is also a Hilbert-Schmidt operator on $\mathscr{H}$.

Let $S_i=K_{x_i}\otimes K_{x_i}-T$. Then $\frac{1}{n}{\sum }_{i=1}^n{S}_i=T_n-T$, and

$𝔼[S_i]={\displaystyle {\int }_X}{K}_x\otimes K_x\nu (\mathrm{d}x)-T=0,$

where the Bochner integral ${\int }_X{K}_x\otimes K_x\nu (\mathrm{d}x)$ converges in the $\parallel \cdot {\parallel }_{\mathrm{HS}}$ norm. Therefore, we can apply the operator Bernstein concentration inequality to deal with the sum of the i.i.d random operators $\{S_1,\mathrm{\dots },S_n\}$ with zero means.