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$.

  • 1
    $\begingroup$ +1, but perhaps mathoverflow fits better? $\endgroup$ – Ilya Jul 16 '13 at 14:45
  • $\begingroup$ Yes, perhaps you're right. I might have to duplicate it there... $\endgroup$ – Alexander Sokol Jul 17 '13 at 9:54

The supremum of a Gaussian process is tricky to handle, and one way to do it is to use chaining1, 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.

1 See for example Chapter 13 of Concentration Inequalities. A Non asymptotic theory of independance, Boucheron, Lugosi, Massart


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.