I am reading the paper [1]. At page 18, eq 115, it is claimed the following:

Given a separable process $(X_t)_{t\in T}$, we have $\lim_{n\to\infty}\mathbb E[\sup_{t\in T}(X_t-X_{\pi_n(t)})]=0$.

Here the only hypothesis on the labelling space $T$ is that it is a bounded metric space. $(X_t)$ is actually assumed to be a subgaussian process, but this fact should not matter for the property stated, or at least the inequality is justified only using the separability in the paper. $\pi_n$ defines a sequence of refining nets. This means that $d(\pi_n(t), t)\leq \varepsilon_n$ for all $t$ and all $n$ (where $d$ is the distance defined on $T$ and $\varepsilon_n$ is a vanishing decreasing positive sequence), and $\pi_n(T)$ is a finite set.

The definition used for separability (Definition 5 in the paper) is the following:

A random process $(X_t)_{t\in T}$ is said separable if there is a countable set $T_0\subseteq T$, dense in $T$, such that $$\mathbb P\left(X_t\in\lim_{s\to t, s\in T_0}X_s, \quad\forall t\in T\right) = 1\,.$$

In the definition above $x\in \lim_{s\to t, s\in T_0}x_s$ means that there is a sequence $x_s$ in $T_0$ which tends to $x$.

Does the separability of a process actually guarantee such a strong convergence of $X_{\pi_n(t)}$ to $X_t$? What strikes me the most is that the separability involves only the existence of a dense subset, which might have nothing to do with the support of the nets $\pi_n(T)$.

The justification of the property given in the paper is

(see proof of Theorem 5.24 in [2]).

However, looking at the referenced proof I could not find anything suggesting that $\lim_{n\to\infty}\mathbb E[\sup_{t\in T}(X_t-X_{\pi_n(t)})]=0$.

Am I actually missing something obvious?

[1] Asadi et al., Chaining Mutual Information and Tightening Generalization Bounds, 2018. https://arxiv.org/abs/1806.03803
[2] Van Handel, Probability in high dimensions. https://web.math.princeton.edu/~rvan/APC550.pdf


1 Answer 1


The inequality $$\lim_{n\to\infty}\mathbb E[\sup_{t\in T}(X_t-X_{\pi_n(t)})]=0 \quad (*) $$ certainly does not follow from separability alone: The indicator of ${\mathbb Q} \cap [0,1]$ is a deterministic separable process with $T_0=\Bigl({\mathbb Q} \cup ({\mathbb Q}+\sqrt{2})\Bigr) \cap [0,1]$. Even seperability and the subgaussian property do not suffice if the metric space is too large. (E.g. consider a Gaussian process indexed by the unit ball $B$ of an infinite dimensional Hilbert space, with $E[(X_t-X_s)^2]=\|t-s\|^2$ for all $t,s \in B$. This process is unbounded in any ball $B(z,r) \subset B$.)

However, if you also assume summability of the series (107) in [1], then $(*)$ does follow, and the proof is analogous to the proof of Theorem 5.24 in [2], using the series (107) instead of the Dudley series, and invoking Theorem 7 of [1] instead of Lemma 5.1 of [2].

  • $\begingroup$ Thank you @Yuval for your answer. However I am still confused and cannot see how to easily pass from the proof in [2] to the conclusion. Could you please detail a bit more? From my understanding, in [2] they control the reminder $E[\sup_{t\in T}(X_t-X_{\pi_n(t)})]$ by using that it is $0$ if $T$ is finite and $n$ large enough. But to use this argument we would need something like $\lim_{n\to\infty}\sup_k E[\sup_{t\in T^{(k)}}(X_t-X_{\pi_n(t)})]=\sup_k\lim_{n\to\infty} E[\sup_{t\in T^{(k)}}(X_t-X_{\pi_n(t)})]=0$, where $T^{(k)}$ are finite subset whose union is $T_0$. But how to show it? $\endgroup$
    – ECL
    Jan 25 at 17:11
  • $\begingroup$ Moreover I don't see how the series (107) helps in solving the question. The random variable $W$ does not appear in (*), so we might choose any random variable like that which is independent of the process, and all the mutual information would always be $0$, making the series (107) summable. $\endgroup$
    – ECL
    Jan 25 at 17:15
  • $\begingroup$ The series (107) helps, with this $W$ in view of Theorem 7 of [1]. Take $T^{(k)}$ as the first $k$ elements of $T_0$ in some enumeration. $\endgroup$ Jan 26 at 17:47

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.