How well can the maximum of a Gaussian process be approximated by a finite-dimensional Gaussian variable?

Question

Consider a compact set $K$ in $\mathbb{R}^p$, and let $W$ be a mean zero continuous Gaussian process on $K$, meaning that $W$ takes its values in the space of continuous functions from $K$ to $\mathbb{R}$, and furthermore, for all $n$ and $x_1,\ldots,x_n\in K$, $(W(x_1),\ldots,W(x_n))$ is Gaussian with mean zero.

Since $K$ is compact, $K$ can be covered by finitely many balls of radius $\varepsilon$. Fix $\varepsilon>0$. Consider such a covering with balls having centers $x_1,\ldots,x_k$.

Question: How well is the distribution of the supremum $\sup_{x\in K}W(x)$ approximated by the maximum $\max_{i\le k}W(x_i)$?

My own interest in this stems from the question of understanding when the supremum norm of a sequence of Gaussian processes converges weakly: I hope to elucidate this by approximating the suprema by finite maxima. It is not a priori clear what a good measure of distance between the distribution of $\sup_{x\in K}W(x)$ and $\max_{i\le k}W(x_i)$ would be. Several possible choices present themselves: For example the total variation distance, the Levy-Prokhorov distance and the Kolmogorov distance. The distribution of $W$ is uniquely specified by its covariance function, so any bound on the distance would naturally be in terms of the covariance function of $W$.

Answer 1

The supremum of a Gaussian process is tricky to handle, and one way to do it is to use chaining¹, which is based on $\epsilon$-net of $K$ for the canonical pseudo-distance: $$d^2(x,y) = \mathbb{V}[W(x)-W(y)] = k(x,x)-2k(x,y)+k(y,y)\,,$$ where $k(x,y)$ denotes the covariance of the GP. With this pseudo-distance in hand, define the covering numbers $N(\epsilon,K,d)$ be the smallest number of balls of size $\epsilon$ wrt $d$ required to cover $K$. Then you have the general upper bound: $$\mathbb{E}[\sup_{x\in K}W(x)] \leq C \int_0^{\sup_{x,y\in K}d(x,y)} \sqrt{\log N(\epsilon,K,d)} \mathrm{d}\epsilon\,.$$ Furthermore if you are given an $\epsilon$-net $x_1,\dots,x_k$, then it is possible to prove that: $$\mathbb{E}[\sup_{x\in K}W(x)-\max_{i \leq k} x_i] \leq C \int_0^\epsilon \sqrt{\log N(\epsilon',K,d)} \mathrm{d}\epsilon'\,.$$ Note that this indeed goes to $0$ when $\epsilon$ tends to $0$. It is also possible to get the high probabilistic counterpart of such bounds (instead of only the expectation).

In your case, the $x_i$ are not an $\epsilon$-net of $K$ with respect to $d$, but with respect to the metric of $K$. Therefore, you first need to provide an upper bound of $d(x,y)$ in terms of the metric of $K$. I advice you to read Grünewälder et. al., (2010), where they answer this question for the case of Bandit Problem.

---

¹ See for example Chapter 13 of **Concentration Inequalities. A Non asymptotic theory of independence**, Boucheron, Lugosi, Massart