2
$\begingroup$

Suppose $\{X_t; t \in \mathcal{X}\}$ is a centered Gaussian Process with covariance function $k(\cdot,\cdot)$, and let $d(x,y) = \mathbb{E}[(X_x-X_y)^2]$.

I am trying to find a tail bound for the suprema of this Gaussian process over a $d$-ball $B(\rho) = \{x \in \mathcal{X}: d(x,0)\leq \rho\}$, i.e., $Pr( \sup_{x \in B(\rho)}X_x \geq S) \leq Ce^{-u}$. Here I want to get an expression for $S$ in terms of $\rho$.

So, for my first attempt I used classical chaining and using bounds on entropy numbers, I think I can say that $S \leq \mathcal{O}(\rho\sqrt{u + C_2\log(1/\rho)})$. ( I followed the formulation in Ch-2 of Talagrand's book)

Since I know that the bounds based on entropy numbers can be loose as compared to $\gamma_2$ given by generic chaining, I found this paper (Link to pdf) by Ramon van Handel which give tighter bounds.

In particular, Corollary 2.7 gives bounds on $\gamma_p$ in terms of entropy numbers of sets $B_t$, and these sets are defined in Corrollary 2.8 as follows:

$B_t = \{ y \in B: \inf_{z \in \partial\|y\|_B}\|z\|^* \leq t\}$. where $\partial\|y\|_B$ is the set of subgradients of $\|.\|_B$ at $y$, and $\|.\|_B$ is the gauge functional of set $B$ (defined on Pg.7 of the paper).

My Question is whether we can write an explicit form of these sets $B_t$ for my setting, for which I can get bounds on entropy numbers?

So to translate this definition to my case, we have the following:

$\langle x, y \rangle = \mathbb{E}[X_x X_y]$

$\|x\| = \mathbb{E}[X_x^2]^{1/2}$

$B = B(\rho)$

$\|x\|_B = \frac{1}{\rho}\|x\|$

$\|z\|^* = \sup_{x:\|x\|\leq 1}\langle x,z\rangle$

$\|z\|^*_B = \sup_{x:\|x\|\leq \rho}\langle x,z\rangle = \rho\|z\|^*$

I am a bit confused at this point. By definition of $\partial\|y\|_B$ given in proof of Corollary 2.8, doesn't it mean that $z= \frac{y}{\rho\|y\|}$ is the only element in $ \partial\|y\|_B$, and $\|z\|^*_B=1$ which implies $\|z\|^* = \frac{1}{\rho}$?

$\endgroup$

1 Answer 1

1
$\begingroup$

Question 1

My Question is whether we can write an explicit form of these sets $B_t$ for my setting, for which I can get bounds on entropy numbers?

It depends. The thin sets $B_t$ are thinned from $B$. As you defined, $B$ can be written as $$B(\rho)=\{x\in\mathcal{X}:\mathbb{E}[(X_{x}-X_{0})^{2}]=\mathbb{E}\left[X_{x}^{2}+X_{0}^{2}-2X_{x}X_{0}\right]=k(x,x)+k(0,0)-2k(x,y)\leq\rho\} $$ according to how you define the covariance $k$, $B(\rho)$ can be convex or not. The final goal is not $B_t$ but $e_n(B)$. If $B$ is convex (it is surely symmetric due to the centered Gaussian setup.), then Theorem 4.1 combined with Theorem 1.2 is what you asked for. However, if you choose some $k$ where $B$ is not convex, then you need to figure out a convex envelope of $B$ and apply Theorem 4.1 onto it again. Concerning $B_t$, you can use a covering of $\ell_p$-ball OR octahedra shown in Sec 3 and take the union bound as a coarser bound.

Question 2

By definition of $\partial\|y\|_B$ given in proof of Corollary 2.8, doesn't it mean that $z= \frac{y}{\rho\|y\|}$ is the only element in $ \partial\|y\|_B$, and $\|z\|^*_B=1$ which implies $\|z\|^* = > \frac{1}{\rho}$?

No. Any $z$ such that $\|z\|^*_B\leq 1$ will do because $B$ is not necessarily smooth when you use the notation $\partial\|y\|_B$. Think of a polygon and $z$ may be a straight line touching the $B$ only at a vertex.

$\endgroup$
4
  • $\begingroup$ Thanks. I think I will first begin with simpler classes of covariance functions, for example covariance functions $k$ such that $k(x,y) = f(\|x-y\|)$ for some norm. $\endgroup$
    – panini
    May 11, 2017 at 17:30
  • $\begingroup$ I have a question. Suppose $d$ is the natural metric of the Gaussian process, and $B(\rho) \subset \mathcal{X}$ is a $d$-ball, where $(\mathcal{X},\|.\|)$ is the Banach space indexing the Gaussian Process. Suppose the set $B(rho)$ is actually a symmetric convex subset of $\mathcal{X}$, and I can get good estimate of $\gamma_2$ with respect to the metric $\|x-y\|$ by Handel's paper. Can I use this to say anything about $\gamma_2$ with respect to the distance function $d$? (I am asking it because in one example I am trying out, $d$ balls correspond to ellipsoids in $\mathcal{X}$) $\endgroup$
    – panini
    May 12, 2017 at 22:36
  • $\begingroup$ The reason I am confused is because in Thm-1.1, $\gamma_2$ is with respect to the natural pseudo-metric $d$ of the Gaussian Process, but for the rest of the paper ( for example Thm.-1.2) he considers $(\mathcal{X},\|.\|)$ to be a Banach space, and computes $\gamma_2$ bounds with respect to $d'(x,y) = \|x-y\|$. For the example in 3.1, he selected the Gaussian Process in such a way that $d$ coincides with the distance induced by $\|.\|_2$ in Euclidean space. So does this mean, these results are only applicable when $d$ is same as the metric induced by $\|.\|$ of some Banach space? $\endgroup$
    – panini
    May 12, 2017 at 23:08
  • $\begingroup$ @panini I guess you cannot directly claim anything about $d$. When they coincide you certainly can, for the case they do not, I do not think so. $\endgroup$
    – Henry.L
    May 12, 2017 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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