Stochastic Processes for ML

Let $(X_t)_{t \in [0,1]^d}$ be a stochastic process such that for some $\alpha, \beta, C > 0$:

$\mathbb{E}[|X_s - X_t|^\alpha] \leq C \|s - t\|^{d + \beta} \quad \text{for all } s, t \in [0,1]^d$

Then $X$ admits a modification $\tilde{X}$ (i.e., $\tilde{X}_t = X_t$ a.s. for each $t$) with sample paths that are locally $\gamma$-Hölder continuous for every $\gamma < \beta/\alpha$.

Source: Karatzas-Shreve (1991), Theorem 2.2.8; Stroock-Varadhan (1979), Theorem 2.1.6.

The criterion translates a moment bound on increments into a path-regularity guarantee. Brownian motion has Gaussian increments with $\mathbb{E}[|B_s - B_t|^\alpha] \asymp |s - t|^{\alpha/2}$ for any $\alpha$, so taking $\alpha$ large gives continuity with $\gamma < 1/2$ — Brownian paths are $(1/2 - \epsilon)$-Hölder for every $\epsilon > 0$, and not better (this is sharp).

For a Gaussian process with kernel satisfying $k(s, s) - 2 k(s, t) + k(t,t) \leq C \|s - t\|^{2\beta}$, all moments $\alpha$ are controlled by the variance, and Kolmogorov gives continuity with Hölder exponent up to $\beta$.

This is the bridge from spectral information (a kernel decay rate) to path-wise information (Hölder regularity of GP samples). For the squared- exponential kernel $k(s, t) = \exp(-\|s-t\|^2/(2\ell^2))$, the canonical metric satisfies $d(s, t) \asymp \|s - t\|/\ell$, so samples are infinitely Hölder. For the Matérn kernel with smoothness $\nu$, samples are exactly $(\nu - \epsilon)$-Hölder.

This determines whether GP regression with a given kernel can recover functions in a corresponding Hölder class, and at what rate.

The criterion is sufficient, not necessary. A process can be continuous without satisfying the moment bound (e.g., almost-surely-constant processes). Conversely, a process whose increment moments fail the criterion may have a discontinuous modification but still be continuous along specific sub-sequences. For non-Gaussian processes with heavy-tailed increments, the criterion can give weaker continuity than the truth.

Let $\mathcal{F}$ be a Donsker class for $P$. Then the empirical process $G_n$ converges in distribution to a centered Gaussian process $G_P$ indexed by $\mathcal{F}$ with covariance $\mathrm{Cov}(G_P(f), G_P(g)) = P(fg) - (Pf)(Pg)$:

$G_n \rightsquigarrow G_P \quad \text{in } \ell^\infty(\mathcal{F})$

Source: van der Vaart-Wellner (1996), Theorem 2.5.2; classical case (empirical CDF, $\mathcal{F} = \{\mathbf{1}_{(-\infty, t]}\}$) is the original Donsker theorem (1952), with $G_P$ the Brownian bridge.

This is the function-space analog of the central limit theorem. For the empirical CDF on the real line, the limit process is the Brownian bridge, which has covariance $k(s, t) = \min(F(s), F(t)) - F(s) F(t)$. For more complex classes (VC, $L_2$-bounded RKHS balls), Donsker's theorem requires the class to be measurable and have finite uniform entropy.

The practical consequence: bounding the finite-sample supremum of $G_n$ via chaining is essentially the same as bounding the supremum of the limit Gaussian process $G_P$. Dudley's entropy integral works for both.

Donsker's theorem is the reason that learning theory results derived for Gaussian processes (Sudakov-Fernique, generic chaining, Borell-TIS concentration) transfer to empirical processes. The two are the same object in the limit, modulo finite-sample corrections.

Concretely, this is what licenses using $\sqrt{n}$-rate Gaussian-process heuristics in finite-sample analysis. Bracketing entropy (van der Vaart- Wellner Sec. 2.7) gives a more refined version that also handles VC and parametric classes.

Donsker's theorem requires the class to be Donsker, which excludes sufficiently rich classes (e.g., the class of all measurable indicator functions, or VC classes of dimension growing with $n$). For non-Donsker classes, you fall back to direct chaining bounds without an asymptotic GP limit.

Let $f^{(L)}(x; \theta) = W^{(L)} \phi(W^{(L-1)} \phi(\cdots \phi(W^{(1)} x + b^{(1)}) \cdots) + b^{(L-1)}) + b^{(L)}$ be a fully-connected network with the random initialization above. As all hidden widths $m_l \to \infty$ jointly, the prelogit output converges in distribution (over the random init) to a centered Gaussian process $f^{(L)} \sim \mathcal{GP}(0, k^{(L)})$ where the NNGP kernel $k^{(L)}$ is defined recursively by:

$k^{(0)}(x, x') = \sigma_w^2 \cdot \frac{x^\top x'}{d_0} + \sigma_b^2$

$k^{(l)}(x, x') = \sigma_w^2 \cdot \mathbb{E}_{(u, v) \sim \mathcal{N}(0, K^{(l-1)})}\!\bigl[\phi(u) \phi(v)\bigr] + \sigma_b^2$

where $K^{(l-1)}$ is the 2×2 covariance matrix $\bigl[\begin{smallmatrix} k^{(l-1)}(x,x) & k^{(l-1)}(x, x') \\ k^{(l-1)}(x',x) & k^{(l-1)}(x',x') \end{smallmatrix}\bigr]$.

Source: Neal (1996) for one hidden layer; Lee, Bahri, Novak, Schoenholz, Pennington, Sohl-Dickstein (2018), "Deep Neural Networks as Gaussian Processes," ICLR; Matthews et al. (2018), "Gaussian Process Behaviour in Wide Deep Neural Networks," ICLR.

At each hidden layer, the activations are sums of $m$ i.i.d. terms (one per neuron). The classical CLT says the sum, scaled by $1/\sqrt{m}$, converges to a Gaussian whose variance equals the per-term variance. This is the key step: at infinite width, every layer's preactivations are Gaussian, and the covariance is determined by the previous layer's covariance through the recursion above.

The recursion is computable in closed form for ReLU (Cho-Saul 2009 arccosine kernel) and analytically for many activations.

The NNGP correspondence enables exact Bayesian inference with infinite-width networks: you compute the NNGP kernel for your architecture, then do GP regression with that kernel. The posterior is in closed form.

The closely related neural tangent kernel captures the training dynamics of infinite-width networks: under gradient flow with infinitesimal learning rate, the NTK is constant during training, and the trained network's predictions equal NTK kernel ridge regression. NNGP is for inference at init; NTK is for training trajectories.

This gives a complete theory of infinite-width networks: they are Gaussian processes both before and (in a different sense) after training. The hard open question is what finite width changes, since real networks have features that infinite-width theory cannot model.

The correspondence holds in the infinite-width limit. At finite width, correction terms appear; the leading correction is $O(1/m)$ for kernel quantities. For modern transformers (where the relevant scaling involves sequence length and depth, not just width), the NNGP correspondence is more delicate; see Yang's "Tensor Programs" series for the modern formulation.

The correspondence does not capture feature learning: in the NNGP/NTK limits, the network's intermediate representations are frozen at their initialization values. Real networks learn features, which is why finite- width theory matters for explaining modern deep learning.

Let $(D_n)_{n \geq 1}$ be a martingale difference sequence with $|D_n| \leq b_n$ a.s. for all $n$. Let $S_n = \sum_{i=1}^n D_i$. Then for all $t > 0$:

$\mathbb{P}(|S_n| \geq t) \leq 2 \exp\!\Bigl(-\frac{t^2}{2 \sum_{i=1}^n b_i^2}\Bigr)$

Source: Azuma (1967), "Weighted sums of certain dependent random variables," Tohoku Math. J. 19; Hoeffding (1963), Theorem 2.

This is Hoeffding's inequality without the independence assumption: the martingale difference structure ($\mathbb{E}[D_i \mid \mathcal{F}_{i-1}] = 0$) replaces independence and gives the same sub-Gaussian tail. The constant $\sum b_i^2$ is the "effective variance bound" in the worst case; Bernstein- type tightening (Freedman's inequality) replaces it with the conditional variance $\sum \mathbb{E}[D_i^2 \mid \mathcal{F}_{i-1}]$.

This is what powers concentration for adaptive ML algorithms: in online learning, the cumulative regret is a martingale by construction (each new loss is centered conditional on the algorithm's prediction), so Azuma- Hoeffding gives anytime regret bounds.

• McDiarmid's inequality (the workhorse for generalization bounds) is proved by applying Azuma-Hoeffding to the Doob martingale of any bounded-differences function.
• Online learning regret bounds: Hedge, EXP3, UCB all rely on Azuma-Hoeffding to control cumulative deviations.
• Stochastic approximation / SGD convergence: noisy gradient terms form an MDS, and Azuma-Hoeffding gives anytime convergence rates.
• Doob martingales for sums under arbitrary dependence: when $f(X_1, \ldots, X_n)$ has bounded differences in each coordinate, the process $M_k = \mathbb{E}[f \mid X_1, \ldots, X_k]$ is a bounded MDS, giving McDiarmid's $\exp(-2t^2 / \sum c_i^2)$ tail.

Azuma-Hoeffding is loose by a factor of 4 compared to McDiarmid's classical form for bounded-differences functions, due to the variance bound $\sum b_i^2$ replacing $\sum (b_i^+ - b_i^-)^2$. For tighter rates, use Freedman's inequality (which replaces $b_i^2$ by predictable quadratic variation) when an MGF moment bound conditional on the filtration is available.