High-Dimensional Probability

High-dimensional probability theory studies a high-dim random vector $X\in {\mathbb{R}}^n$ and its transformation (high-dim functions). Without any additional structure, there is nothing special about this random vector. In high-dim probability, we always assume $X$ has independent (or weakly dependent) coordinates, i.e., $X=(X_1,\dots ,X_n)$ where $X_i$ are independent random variables. Suppose $X_i$ are iid, the very first result we have is regarding its variance:

$$\mathrm{Var}(X)=\mathrm{Cov}(X_1,\dots ,X_n)=n\mathrm{Var}(X_1).$$

Such a factorization into the dimension $n$ and one-dim property is called tensorization, a key technique in high-dimensional probability.

For the transformation of such high-dim random vectors, high-dimensional probability theory studies high-dimensional functions of the form

$$f(X_1,\dots ,X_n).$$

Provided that $f$ is “smooth” enough, we expect Concentration of Measure, i.e., $f(X)\approx \mathbb{E}[f(X)]$. Provided that $f$ is not too “complex”, we can express it as a Suprema of Stochastic Processes, and bound its expectation by its “complexity”.

Applications

• Statistical Learning
• Compressed sensing
• random matrices
  • covariance matrix
  • random graphs
• Sampling
• Optimal transport
• Gaussian approximation

Concentration of Measure

Consider the simplest form: $f(x_1,\dots ,x_n)=\frac{1}{n}{\sum }_{i=1}^n{x}_i$. If $\{X_i{\}}_{i=1}^{\infty }$ is IID and has a finite mean, by the strong Central Limit Theorem, we know $f(X)\stackrel{a.s.}{\to }\mathbb{E}[X_1]$. We ask

Qn

1. How about general functions?
2. How fast is this convergence? (non-asymptotic)

Informal Principle

If $X=\{X_i{\}}_{i=1}^n$ is IID, then $f(X)\approx \mathbb{E}f(X)$ provided that $f$ is “smooth” enough, i.e., $f$ does not depend too heavily on any of its coordinates.

• Chebyshev Inequality
• Hoeffding’s Inequality
  • Azuma
• Poincare Inequality
• Chernoff Bound
• Sobolev Inequality
• Transportation Inequality

Suprema of Stochastic Processes

Qn

How large is $\mathbb{E}f(X)$?

Ex

• L2 error: $\Vert X-\hat{X}{\Vert }_2={\sup }_{v\in S^{d-1}}\left|⟨v,(X-\hat{X})v⟩\right|$.
• Convex conjugate: $f^{\ast }(x)={\sup }_{y\in {\mathbb{R}}^n}\{⟨y,x⟩-f(y)\}$

The prevalence of suprema is related to the variational principle, which transform the original problem into an Optimization problem, with the original solution corresponding to a supremum.

Informal Principle

If $t\mapsto Y_t$ is “smooth”, then $\mathbb{E}[{\sup }_{t\in T}{Y}_t]$ can be controlled by the complexity of $T$.