# Majorizing Measures, Codes, and Information

Yifeng Chu and Maxim Raginsky The authors are with the Department of
Electrical and Computer Engineering and the Coordinated Science Laboratory,
University of Illinois, Urbana, IL 61801, USA. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>work was supported by the Illinois Institute for Data
Science and Dynamical Systems (iDS2), an NSF HDR TRIPODS institute, under
award CCF-1934986.

###### Abstract

The majorizing measure theorem of Fernique and Talagrand is a fundamental
result in the theory of random processes. It relates the boundedness of random
processes indexed by elements of a metric space to complexity measures arising
from certain multiscale combinatorial structures, such as packing and covering
trees. This paper builds on the ideas first outlined in a little-noticed
preprint of Andreas Maurer to present an information-theoretic perspective on
the majorizing measure theorem, according to which the boundedness of random
processes is phrased in terms of the existence of efficient variable-length
codes for the elements of the indexing metric space.

##  I Introduction

Let $(T,d)$ be a compact metric space, and let $(X_{t})_{t\in T}$ be a zero-
mean random process indexed by the elements of $T$ and satisfying the
increment condition

$\displaystyle\mathbf{P}\Big{[}|X_{s}-X_{t}|\geq ud(s,t)\Big{]}\leq
2e^{-u^{2}},\quad s,t\in T,\,u>0.$ (1)

The question of boundedness of the expected supremum $\mathbf{E}[\sup_{t\in
T}X_{t}]$ arises in a variety of applications, such as high-dimensional
probability, convex geometry, functional analysis, theoretical computer
science, mathematical statistics, and learning theory [1]. A fundamental
result of Fernique [2] and Talagrand [3] states that, for any fixed but
arbitrary $t_{0}\in T$,

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in
T}|X_{t}-X_{t_{0}}|\Big{]}\lesssim\inf_{\mu\in\mathcal{P}(T)}\sup_{t\in
T}I_{\mu}(t),$ (2)

where $\mathcal{P}(T)$ is the set of all Borel probability measures on $T$,

$\displaystyle I_{\mu}(t)\mathrel{\mathop{\mathchar 58\relax}}=\int^{{\rm
diam}(T)}_{0}\sqrt{\log\frac{1}{\mu(B(t,\varepsilon))}}\operatorname{d\\!}\varepsilon$
(3)

is the Fernique–Talagrand functional, and $a\lesssim b$ indicates that $a\leq
Cb$ for some absolute constant $C>0$. Here, ${\rm
diam}(T)\mathrel{\mathop{\mathchar
58\relax}}=\sup\\{d(s,t)\mathrel{\mathop{\mathchar 58\relax}}s,t\in T\\}$ is
the (finite) diameter of $T$, $B(t,\varepsilon)$ denotes the closed ball of
radius $\varepsilon$ centered at $t$, and the logarithm is taken to base $2$.
Moreover, if $(X_{t})_{t\in T}$ is a Gaussian process and $T$ is endowed with
the canonical metric

$\displaystyle d(s,t)\mathrel{\mathop{\mathchar
58\relax}}=\sqrt{\mathbf{E}[(X_{s}-X_{t})^{2}]},$ (4)

then the bound (2) can be reversed [3]:

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in
T}|X_{t}-X_{t_{0}}|\Big{]}\gtrsim\inf_{\mu\in\mathcal{P}(T)}\sup_{t\in
T}I_{\mu}(t).$ (5)

The inequality (2) says that the expected supremum of $(X_{t})$ is bounded
provided there exists at least one $\mu\in\mathcal{P}(T)$, such that
$\sup_{t\in T}I_{\mu}(t)<\infty$ (such probability measures are called
majorizing measures); moreover, for Gaussian processes, the existence of a
majorizing measure is equivalent to boundedness of expected suprema.

While the Fernique–Talagrand functional provides sharp bounds on the expected
supremum of $(X_{t})$, the machinery of majorizing measures was eventually
replaced by an equivalent combinatorial framework involving various multiscale
discrete structures, such as covering and packing trees (see, e.g., [4] or [1,
Ch. 6]). In a little-noticed preprint [5], A. Maurer has provided an
alternative information-theoretic perspective on majorizing measures starting
from the observation that the integrand in (3) has an information-theoretic
flavor–indeed, $\log\frac{1}{\mu(B(t,\varepsilon))}$ is (roughly) proportional
to the number of bits one would use to localize a point $t\in T$ up to a ball
of radius $\varepsilon$ when given a ‘prior’ probability measure
$\mu\in\mathcal{P}(T)$. Building on this intuition, Maurer used the well-known
correspondence between probability measures and uniquely decodable codes on a
discrete (finite or countably infinite) alphabet [6, Sec. 5.5] to show that
the Fernique–Talagrand functional can be bounded both from above and from
below in terms of information-theoretic quantities pertaining to sequences of
variable-length lossy codes on $T$ that allow for arbitrarily accurate
reconstruction of the points $t\in T$ using sufficiently long codewords, with
the metric $d$ playing the role of the fidelity criterion [7].

In this paper, we develop this perspective further by giving a more direct
construction of multiscale variable-length codes that allows us to seamlessly
recover a number of existing bounds on expected suprema. Moreover, we derive
an information-theoretic version of the lower bound (5) for Gaussian
processses that matches our upper bounds up to a multiplicative constant. In
terms of applications, we expect these results to be of use in analyzing the
statistical performance of machine learning algorithms through the lens of
data compression and the Minimum Description Length principle [8, 9].

##  II Preliminaries

###  II-A Variable-length codes on metric spaces

Let a compact metric space $(T,d)$ be given, with ${\rm diam}(T)=1$. A
variable-length code (VLC) on $T$ is a pair $(\pi,f)$, where
$\pi\mathrel{\mathop{\mathchar 58\relax}}T\to T$ is a mapping whose image
$\pi(T)$ is a discrete subset of $T$ and $f\mathrel{\mathop{\mathchar
58\relax}}\pi(T)\to\\{0,1\\}^{*}$ is a uniquely decodable representation of
the elements of $\pi(T)$ by finite-length binary strings. In particular, it
satifsies the Kraft–McMillan inequality

$\displaystyle\sum_{s\in\pi(T)}2^{-\ell(f(s))}\leq 1,$ (6)

where $\ell(\cdot)$ denotes the length of a binary string. We say that a VLC
$(\pi,f)$ operates at resolution $\rho\geq 0$ if $d(t,\pi(t))\leq\rho$ for all
$t\in T$ (if $\rho=0$, then $T$ is necessarily discrete, and $(\pi,f)$ is
lossless). A natural procedure for constructing such VLC’s is to fix a
$\rho$-partition $\mathcal{A}$ of $T$, i.e., a family of disjoint subsets
$A\subseteq T$ of diameter at most $\rho$ whose union is all of $T$; if
$\rho>0$, then it is always possible to find a finite partition by compactness
of $T$. Then, picking a point $s_{A}$ in each $A\in\mathcal{A}$, we take
$\pi(t)\mathrel{\mathop{\mathchar 58\relax}}=s_{A(t)}$, where $A(t)$ is the
unique element of $\mathcal{A}$ that contains $t$. The mapping $\pi$
constructed in this way is evidently idempotent, i.e., $\pi\circ\pi=\pi$.
Finally, with $\pi(T)=\\{s_{A}\mathrel{\mathop{\mathchar
58\relax}}A\in\mathcal{A}\\}$, we can choose any mapping
$f\mathrel{\mathop{\mathchar 58\relax}}\pi(T)\to\\{0,1\\}^{*}$ that satisfies
(6). For instance, we can pick any $\mu\in\mathcal{P}(T)$ such that $\mu(A)>0$
for all $A\in\mathcal{A}$ and let $f$ be the Shannon code with codelengths
$\ell(f(s_{A}))=\lceil\log\frac{1}{\mu(A)}\rceil,A\in\mathcal{A}$.

We will be working with sequences of VLC’s that operate at multiple scales. We
will say that $\mathcal{C}=\\{(\pi_{k},f_{k})\\}_{k\in\mathbb{N}}$ is
admissible if the following conditions are satisfied:

  * (i)

for each $k\in\mathbb{N}$, $\pi_{k}$ is idempotent and there exists a mapping
$\varphi_{k|k+1}\mathrel{\mathop{\mathchar 58\relax}}T\to T$, such that
$\pi_{k}=\varphi_{k|k+1}\circ\pi_{k+1}$;

  * (ii)

$(\pi_{k},f_{k})$ operates at resolution $\rho_{k}$, and $\rho_{k}\to 0$ as
$k\to\infty$;

  * (iii)

for each $t$ and each $k$,
$\ell(f_{k}\circ\pi_{k}(t))\leq\ell(f_{k+1}\circ\pi_{k+1}(t))$.

We also define $(\pi_{0},f_{0})$ with $\pi_{0}(T)=\\{t_{0}\\}$ and
$\ell(f_{0}(t_{0}))=0$ for a fixed but arbitrary point $t_{0}\in T$. Condition
(i) says that, for each $t$, the encoding $\pi_{k}(t)$ can be determined from
any $\pi_{m}(t)$, $m>k$, without knowledge of $t$. We can take
$\varphi_{k|k+1}=\pi_{k}$ without loss of generality since
$\pi_{k}=\varphi_{k|k+1}\circ\pi_{k+1}=\varphi_{k|k+1}\circ\pi_{k+1}\circ\pi_{k+1}=\pi_{k}\circ\pi_{k+1}$.
This implies that the partition $\mathcal{A}_{k+1}$ induced by $\pi_{k+1}$ is
a refinement of $\mathcal{A}_{k}$, and for each $t\in T$ the sets $A_{k}(t)$
(of diameter $\rho_{k}$) are nested, i.e., $T\equiv A_{0}(t)\supseteq
A_{1}(t)\supseteq A_{2}(t)\supseteq\dots$. Conditions (i) and (ii) imply that
$\rho_{k}\searrow 0$ as $k\to\infty$. Finally, condition (iii) constrains the
binary descriptions of each $t$ to become more ‘informative’ as $k$ increases.

A natural procedure for constructing an admissible sequence of VLC’s is to
start with an increasing sequence $(\mathcal{A}_{k})_{k\geq 1}$ of partitions
of $T$ such that each $A\in\mathcal{A}_{k}$ has diameter at most $\rho_{k}$,
with $\rho_{k}\searrow 0$ as $k\to\infty$. The mappings $\pi_{k}$ are
constructed exactly in the same manner as for a single partition, so that
conditions (i)–(ii) will be satisfied automatically. To construct the binary
encodings $f_{k}$ satisfying condition (iii), choose some
$\mu_{1}\in\mathcal{P}(T)$ such that $\mu_{1}(A)>0$ for all
$A\in\mathcal{A}_{1}$; then, for each $k\geq 1$ and each
$B\in\mathcal{A}_{k}$, choose a probability measure
$\nu_{k+1}(\cdot|B)\in\mathcal{P}(T)$ such that $\nu_{k+1}(A|B)>0$ for each
$A\in\mathcal{A}_{k+1}(B)\mathrel{\mathop{\mathchar
58\relax}}=\\{A\in\mathcal{A}_{k+1}\mathrel{\mathop{\mathchar
58\relax}}A\subseteq B\\}$ and $0$ otherwise. This defines a sequence of
probability measures $(\mu_{k})_{k\geq 1}$ by

$\displaystyle\mu_{k+1}(\cdot)$
$\displaystyle=\sum_{B\in\mathcal{A}_{k}}\nu_{k+1}(\cdot|B)\mu_{k}(B),$ (7)

and we can choose each $f_{k}$ so that (ignoring the rounding issues) for each
$t\in T$ and each $k$ we have

$\displaystyle\ell(f_{k+1}\circ\pi_{k+1}(t))\approx\log\frac{1}{\mu_{k+1}(A_{k+1}(t))}$
$\displaystyle\quad=\log\frac{1}{\mu_{k}(A_{k}(t))}+\log\frac{1}{\nu_{k+1}(A_{k+1}(t)|A_{k}(t))}$
$\displaystyle\quad\geq\log\frac{1}{\mu_{k}(A_{k}(t))}$
$\displaystyle\quad\approx\ell(f_{k}\circ\pi_{k}(t)),$

where in the second line we have used the fact that
$A_{k+1}(t)\in\mathcal{A}_{k+1}(A_{k}(t))$, and therefore
$\mu_{k+1}(A_{k+1}(t))=\nu_{k+1}(A_{k+1}(t)|A_{k}(t))\mu_{k}(A_{k}(t))$.

###  II-B Some facts about the Fernique–Talagrand functional

The Fernique–Talagrand functional (3) can be expressed in terms of increasing
sequences of partitions. To that end, following Bednorz [10], we define the
following functional on pairs of probability measures
$\mu,\nu\in\mathcal{P}(T)$:

$\displaystyle M(\mu,\nu)\mathrel{\mathop{\mathchar
58\relax}}=\int_{T}\int^{1}_{0}\sqrt{\log\frac{1}{\mu(B(t,\varepsilon))}}\operatorname{d\\!}\varepsilon\,\nu(\operatorname{d\\!}t).$

Then $I_{\mu}(t)=M(\mu,\delta_{t})$, where $\delta_{t}$ is the Dirac measure
centered at $t$, and the bounds (2) and (5) can be expressed as

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in
T}X_{t}\Big{]}\lesssim\inf_{\mu}\sup_{t}M(\mu,\delta_{t})=\inf_{\mu}\sup_{\nu}M(\mu,\nu)$

and (for Gaussian processes on $T$ with the induced metric)

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in
T}X_{t}\Big{]}\gtrsim\inf_{\mu}\sup_{t}M(\mu,\delta_{t})=\inf_{\mu}\sup_{\nu}M(\mu,\nu).$

We then have the following upper bounds on $I_{\mu}(t)$ and $M(\mu,\nu)$ [10]:
Let $\mathcal{A}=(\mathcal{A}_{k})_{k\geq 1}$ be an increasing sequence of
partitions of $T$, such that ${\rm diam}(A)\leq r^{-k}$ for all
$A\in\mathcal{A}_{k}$ and all $k$ for some $r>1$. Then, setting
$\mathcal{A}_{0}=\\{T\\}$, we have

$\displaystyle
I_{\mu}(t)\leq\sum_{k>0}r^{-k+1}\sqrt{\log\frac{\mu(A_{k-1}(t))}{\mu(A_{k}(t))}}$

and

$\displaystyle
M(\mu,\nu)\leq\sum_{k>0}r^{-k+1}\sum_{B\in\mathcal{A}_{k-1}}\sum_{A\in\mathcal{A}_{k}(B)}\nu(A)\sqrt{\log\frac{\mu(B)}{\mu(A)}}.$

We can express these bounds in information-theoretic terms. Let us define, for
any $k\geq 1$ and any $B\in\mathcal{A}_{j}$ with $j<k$, the entropy and the
cross-entropy

$\displaystyle H_{\mathcal{A}_{k}|B}(\mu)$
$\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=-\sum_{A\in\mathcal{A}_{k}}\mu(A|B)\log\mu(A|B),$ $\displaystyle
H_{\mathcal{A}_{k}|B}(\mu,\nu)$ $\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=-\sum_{A\in\mathcal{A}_{k}}\mu(A|B)\log\nu(A|B).$

Using Jensen’s inequality and the bound
$\inf_{\mu}\sup_{t}M(\mu,\delta_{t})\leq\sup_{\mu}M(\mu,\mu)$ [11, 10], we can
obtain the following:

######  Proposition 1.

For any $r>1$,

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in T}X_{t}\Big{]}$
$\displaystyle\qquad\lesssim\inf_{\mathcal{A}}\sup_{\mu}\sum_{k>0}r^{-k+1}\sum_{B\in\mathcal{A}_{k-1}}\mu(B)\sqrt{H_{\mathcal{A}_{k}|B}(\mu)},$

where the infimum is over all increasing sequences
$\mathcal{A}=(\mathcal{A}_{k})_{k\geq 1}$ of partitions of $T$ with ${\rm
diam}(A)\leq r^{-k}$ for all $A\in\mathcal{A}_{k},k\geq 1$.

##  III The upper bound and some consequences

To keep things simple, we will assume for the remainder of the paper that $T$
is finite (the case of infinite $T$ is not much more difficult under the mild
assumption of separability of all relevant random processes). Let
$\mathcal{C}=\\{(\pi_{k},f_{k})\\}_{k\in\mathbb{N}}$ be an admissible sequence
of VLC’s on $T$, where each $(\pi_{k},f_{k})$ operates at resolution
$\rho_{k}$. Let also $\boldsymbol{p}=(p_{k})_{k\geq 1}$ be a positive
probability mass function on $\mathbb{N}$ and define the functional

$\displaystyle\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}(t)$
$\displaystyle\mathrel{\mathop{\mathchar
58\relax}}=\sum_{k>0}\rho_{k-1}\sqrt{\ln\frac{2^{\ell(f_{k}\circ\pi_{k}(t))+1}}{p_{k}}},$
(8)

where we have set $\rho_{0}={\rm diam}(T)\equiv 1$. The following is a
generalization of [5, Thm. 6]:

######  Theorem 1.

Let $(X_{t})_{t\in T}$ be a centered random process satisfying the increment
condition (1). Let $(\mathcal{C},\boldsymbol{p})$ be such that
$\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}(t)$ is finite for all $t\in T$.
Fix an arbitrary point $t_{0}\in T$. Then, for any $u>0$,

$\displaystyle|X_{t}-X_{t_{0}}|\leq\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}(t)(u+1),\qquad\forall
t\in T$

with probability at least $1-e^{-u^{2}}$.

###### Proof.

Since $T$ is finite, for each $t\in T$ there exists some
$k=k(t)\in\mathbb{N}$, such that $t=\pi_{k}(t)=\pi_{k+1}(t)=\dots$. Therefore
we can form the chaining decomposition [1, p. 19]

$\displaystyle X_{t}-X_{t_{0}}=\sum_{k>0}(X_{\pi_{k}(t)}-X_{\pi_{k-1}(t)}).$

For each $k$, let $S_{k}\mathrel{\mathop{\mathchar 58\relax}}=\pi_{k}(T)$ and
define $\xi_{k}\mathrel{\mathop{\mathchar 58\relax}}S_{k}\to\mathbb{R}$ by

$\displaystyle\xi_{k}(s)\mathrel{\mathop{\mathchar
58\relax}}=d(s,\pi_{k-1}(s))\sqrt{\ln\frac{2^{\ell(f_{k}(s))+1}}{p_{k}}+u^{2}}$

and the event $E_{k}\mathrel{\mathop{\mathchar 58\relax}}=\big{\\{}\exists
s\in S_{k}\mathrel{\mathop{\mathchar
58\relax}}|X_{s}-X_{\pi_{k-1}(s)}|>\xi_{k}(s)\big{\\}}$. Using the increment
condition (1) and the Kraft–McMillan inequality, we have

$\displaystyle\mathbf{P}[E_{k}]$ $\displaystyle\leq\sum_{s\in
S_{k}}\mathbf{P}[|X_{s}-X_{\pi_{k-1}(s)}|>\xi_{k}(s)]$ $\displaystyle\leq
2\sum_{s\in
S_{k}}\exp\Bigg{(}-\frac{\xi^{2}_{k}(s)}{d^{2}(s,\pi_{k-1}(s))}\Bigg{)}$
$\displaystyle=2\sum_{s\in
S_{k}}\exp\Bigg{(}-\ln\frac{2^{\ell(f_{k}(s))+1}}{p_{k}}-u^{2}\Bigg{)}$
$\displaystyle=p_{k}e^{-u^{2}}\sum_{s\in S_{k}}2^{-\ell(f_{k}(s))}$
$\displaystyle\leq p_{k}e^{-u^{2}}.$

Then

$\displaystyle\mathbf{P}\Bigg{[}\exists t\in
T,\,|X_{t}-X_{t_{0}}|>\sum_{k>0}\xi_{k}(\pi_{k}(t))\Bigg{]}$
$\displaystyle\leq\mathbf{P}\Bigg{[}\exists t\in
T,\,\sum_{k>0}\Bigg{(}|X_{\pi_{k}(t)}-X_{\pi_{k-1}(t)}|-\xi_{k}(\pi_{k}(t))\Bigg{)}>0\Bigg{]}$
$\displaystyle\leq\mathbf{P}\Bigg{[}\bigcup_{k}E_{k}\Bigg{]}$
$\displaystyle\leq e^{-u^{2}},$

where the last step follows from the assumption on the weights $p_{k}$. Thus,
since $d(\pi_{k}(t),\pi_{k-1}(t))\leq\rho_{k-1}$,

$\displaystyle|X_{t}-X_{t_{0}}|\leq\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}(t)+u\sum_{k>0}\rho_{k-1},\quad\forall
t\in T$

with probability at least $1-e^{-u^{2}}$. Since
$\ell(f_{k}\circ\pi_{k}(t))\geq 1$ for $k\geq 1$ by the unique decodability of
$f_{k}\mathrel{\mathop{\mathchar 58\relax}}S_{k}\to\\{0,1\\}^{*}$, it follows
that $\frac{2^{\ell(f_{k}\circ\pi_{k}(t))+1}}{p_{k}}\geq 4$, and thus

$\displaystyle\sum_{k>0}\rho_{k-1}\leq\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}(t)$

for all $t\in T$. This completes the proof. ∎

######  Corollary 1.

Under the same assumptions as in Theorem 1,

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in T}X_{t}\Big{]}\leq
2\inf_{(\mathcal{C},\boldsymbol{p})}\sup_{t\in
T}\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}(t).$

###### Proof.

Let $\bar{a}\mathrel{\mathop{\mathchar 58\relax}}=\sup_{t\in
T}\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}(t)$ and
$\bar{Z}\mathrel{\mathop{\mathchar 58\relax}}=\sup_{t\in T}|X_{t}-X_{t_{0}}|$.
By Thm. 1, $\mathbf{P}[\bar{Z}>\bar{a}+u]\leq e^{-u^{2}/\bar{a}^{2}}$ for all
$u>0$, so

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in T}X_{t}\Big{]}$
$\displaystyle=\mathbf{E}\Big{[}\sup_{t\in T}(X_{t}-X_{t_{0}})\Big{]}$
$\displaystyle\leq\mathbf{E}[\bar{Z}]$
$\displaystyle=\int^{\infty}_{0}\mathbf{P}[\bar{Z}>r]\operatorname{d\\!}r$
$\displaystyle=\int^{\bar{a}}\mathbf{P}[\bar{Z}>r]\operatorname{d\\!}r+\int^{\infty}_{\bar{a}}\mathbf{P}[\bar{Z}>r]\operatorname{d\\!}r$
$\displaystyle\leq\bar{a}+\int^{\infty}_{0}e^{-u^{2}/\bar{a}^{2}}\operatorname{d\\!}u$
$\displaystyle\leq 2\bar{a}.$

Now take the infimum over all $(\mathcal{C},\boldsymbol{p})$. ∎

###  III-A Some consequences

A close examination of the proof of Theorem 1 shows that we have not exploited
all of the properties of admissible sequences of VLC’s. To obtain further
results, it will be convenient to decompose the functional
$\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}$ as follows:

$\displaystyle\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}(t)\leq\sigma_{\mathcal{C}}(t)+\sigma^{\prime}_{(\mathcal{C},\boldsymbol{p})}(t)$
$\displaystyle\quad\mathrel{\mathop{\mathchar
58\relax}}=\sum_{k>0}\rho_{k-1}\sqrt{\ell(f_{k}\circ\pi_{k}(t))}+\sum_{k>0}\rho_{k-1}\sqrt{\ln\frac{2}{p_{k}}}$

We can always choose $\boldsymbol{p}$ so that
$\sigma^{\prime}_{(\mathcal{C},\boldsymbol{p})}(t)$ can be upper-bounded by an
absolute constant–e.g., with $p_{k}=2^{-k}$ and $\rho_{k}=r^{-k}\leq 2^{-k}$,
we will have

$\displaystyle\sigma^{\prime}_{(\mathcal{C},\boldsymbol{p})}(t)\leq\sum_{k>0}2^{-k+1}\sqrt{(k+1)\ln
2}\leq 3.$

Thus, in what follows we can focus on $\sigma_{\mathcal{C}}(t)$.

######  Theorem 2.

Let $\mathcal{C}=\\{(\pi_{k},f_{k})\\}_{k\geq 1}$ be an admissible sequence of
VLC’s with $\rho_{k}=r^{-k}$ for some $r\geq 2$. Then

$\displaystyle\\!\\!\sigma_{\mathcal{C}}(t)\lesssim\sum_{k>0}r^{-k+1}\sqrt{\ell(f_{k}\circ\pi_{k}(t))-\ell(f_{k-1}\circ\pi_{k-1}(t))}.$
(9)

###### Proof.

Let $\ell_{k}(t)\mathrel{\mathop{\mathchar
58\relax}}=\ell(f_{k}\circ\pi_{k}(t))$, with $\ell_{0}(t)\equiv 0$. By
admissibility of $\mathcal{C}$, $(\ell_{k}(t))_{k\geq 1}$ is a nondecreasing
sequence of positive integers. Therefore,

$\displaystyle\sigma_{\mathcal{C}}(t)=\sum_{k>0}r^{-k+1}\sqrt{\ell_{k}(t)}$
$\displaystyle\leq\sum_{k>0}r^{-k+1}\sqrt{\ell_{k}(t)-\ell_{k-1}(t)}+\sum_{k>0}r^{-k+1}\sqrt{\ell_{k-1}(t)}$
$\displaystyle=\sum_{k>0}r^{-k+1}\sqrt{\ell_{k}(t)-\ell_{k-1}(t)}+r^{-1}\sigma_{\mathcal{C}}(t),$

which, together with $(1-r^{-1})^{-1}\leq 2$, gives (9). ∎

For each $k>0$, the quantity under the square root in the upper bound (9) is
the extra codelength needed to refine the description $\pi_{k-1}(t)$ at
resolution $r^{-k+1}$ to a more accurate one $\pi_{k}(t)$ at resolution
$r^{-k}$. Several existing results from the literature can now be obtained as
special cases.

First, we can recover the upper bound in terms of labeled nets [4, 12]. A
labeled net on $(T,d)$ is a pair $(\mathcal{A},L)$, where
$\mathcal{A}=(\mathcal{A}_{k})_{k\geq 1}$ is an increasing sequence of
partitions of $T$, such that ${\rm diam}(A)\leq r^{-k}$ for all
$A\in\mathcal{A}_{k}$ and all $k\geq 1$, and $L\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}\to\mathbb{N}$ is a labeling function satisfying the
condition $\\{L(A)\mathrel{\mathop{\mathchar
58\relax}}A\in\mathcal{A}_{k+1}(B)\\}=\\{1,\ldots,|\mathcal{A}_{k+1}(B)|\\}$
for all $B\in\mathcal{A}_{k}$ and all $k$.

######  Theorem 3.

For each labeled net $(\mathcal{A},L)$, there exists an admissible sequence of
VLC’s, such that

$\displaystyle\sigma_{\mathcal{C}}(t)\leq c_{1}\sum_{k>0}r^{-k+1}\sqrt{\log
L(A_{k}(t))}+c_{2},$ (10)

where $c_{1},c_{2}>0$ are universal constants.

###### Proof.

We will use the construction described in Section II-A. To that end, define a
subprobability measure

$\displaystyle\mu^{\prime}_{1}(\cdot)=\frac{6}{\pi^{2}}\sum_{A\in\mathcal{A}_{1}}\frac{1}{L^{2}(A)|A|}{\mathbf{1}}_{A}(\cdot)$

so that $\mu^{\prime}_{1}(A)=\frac{6}{\pi^{2}L^{2}(A)}$ for each
$A\in\mathcal{A}_{1}$, and, for each $k$ and $B\in\mathcal{A}_{k}$, a
subprobability measure

$\displaystyle\nu^{\prime}_{k+1}(\cdot|B)\mathrel{\mathop{\mathchar
58\relax}}=\frac{6}{\pi^{2}}\sum_{A\in\mathcal{A}_{k+1}(B)}\frac{1}{L^{2}(A)|A|}{\mathbf{1}}_{A}(\cdot),$

so that $\nu^{\prime}_{k+1}(A|B)=\frac{6}{\pi^{2}L^{2}(A)}$ for every
$A\in\mathcal{A}_{k+1}(B)$. Consequently, there exist probability measures
$\mu_{1}(\cdot)\geq\mu^{\prime}_{1}(\cdot)$ and
$\nu_{k+1}(\cdot|B)\geq\nu^{\prime}_{k+1}(\cdot|B)$. Then, with $\mu_{k}$
defined recursively via (7), we have

$\displaystyle\ell(f_{k+1}\circ\pi_{k+1}(t))-\ell(f_{k}\circ\pi_{k}(t))$
$\displaystyle\leq\log\frac{1}{\mu_{k+1}(A_{k+1}(t))}-\log\frac{1}{\mu_{k}(A_{k}(t))}+1$
$\displaystyle=\log\frac{1}{\nu_{k+1}(A_{k+1}(t))|A_{k}(t))}+1$
$\displaystyle\leq\log\frac{1}{\nu^{\prime}_{k+1}(A_{k+1}(t)|A_{k}(t))}+1$
$\displaystyle\leq 2\log L(A_{k+1}(t))+\log\frac{\pi^{2}}{6}+1$

The inequality (10) then follows from Theorem 2. ∎

In a similar way, we can recover a bound of Bednorz [10] that involves an
increasing partition just like above:

######  Theorem 4.

For each sequence of partitions as in Theorem 3 and each
$\mu\in\mathcal{P}(T)$, there exists an admissible sequence $\mathcal{C}$ of
VLC’s, such that

$\displaystyle\sigma_{\mathcal{C}}(t)\leq\sum_{k>0}r^{-k+1}\sqrt{\log\frac{\mu(A_{k-1}(t))}{\mu(A_{k}(t))}}+2$
(11)

###### Proof.

Without loss of generality, we may assume that $\mu(A)>0$ for all
$A\in\mathcal{A}_{k}$ and all $k$. We follow the same steps as in the proof of
Theorem 2, but take $\mu_{1}=\mu$ and $\nu_{k+1}(\cdot|B)=\mu(\cdot|B)$ for
all $k$ and all $B\in\mathcal{A}_{k}$. Then, for every $B\in\mathcal{A}_{k}$
and $A\in\mathcal{A}_{k+1}(B)$,
$\nu_{k+1}(A|B)=\mu(A|B)=\frac{\mu(A)}{\mu(B)}$, and

$\displaystyle\ell(f_{k+1}\circ\pi_{k+1}(t))-\ell(f_{k}\circ\pi_{k}(t))$
$\displaystyle\leq\log\frac{\mu(A_{k}(t))}{\mu(A_{k+1}(t))}+1$
$\displaystyle=\log\frac{\mu(A_{k}(t))}{\mu(A_{k+1}(t))}+1.$

Summing over $k$, we get (11). ∎

In fact, there is no loss of generality in working with admissible sequences
of VLC’s constructed from a single $\mu\in\mathcal{P}(T)$ rather than from a
recursively defined sequence $(\mu_{k})_{k\geq 1}$:

######  Theorem 5.

For any $\boldsymbol{p}=(p_{k})_{k\geq 1}$ and any admissible sequence
$\mathcal{C}=\\{(\pi_{k},f_{k})\\}_{k\geq 1}$ of VLC’s constructed from an
increasing sequence of partitions $\mathcal{A}=(\mathcal{A}_{k})_{k\geq 0}$
and a sequence of probability measures $(\mu_{k})_{k\geq 1}$ via (7), there
exists a probability measure $\mu\in\mathcal{P}(T)$ and an admissible sequence
$\mathcal{C}^{\prime}=\\{(\pi^{\prime}_{k},f^{\prime}_{k})\\}_{k\geq 1}$ of
VLC’s, such that

$\displaystyle\bar{\sigma}_{(\mathcal{C}^{\prime},\boldsymbol{p})}(t)\leq\bar{\sigma}_{(\mathcal{C},\boldsymbol{p})}(t)+\sum_{k>0}r^{-k+1}\sqrt{\log\frac{2}{p_{k}}},\quad
t\in T.$ (12)

###### Proof.

Let $\mathcal{C}=\\{(\pi_{k},f_{k})\\}_{k\geq 1}$ be constructed from
$\mathcal{A}$ and $(\mu_{k})_{k\geq 1}$ as indicated. Given $\boldsymbol{p}$,
form the mixture $\mu=\sum_{k>0}p_{k}\mu_{k}$. Then, keeping the same sequence
of partitions $\mathcal{A}=(\mathcal{A}_{k})_{k\geq 1}$, construct
$\mathcal{C}^{\prime}=\\{(\pi^{\prime}_{k},f^{\prime}_{k})\\}_{k\geq 1}$ with
$\pi^{\prime}_{k}=\pi_{k}$ and $f^{\prime}_{k}$ satisfying
$\ell(f^{\prime}_{k}\circ\pi^{\prime}_{k}(t))=\lceil\log\frac{1}{\mu(A_{k}(t))}\rceil$
for every $t\in T$ and every $k\in T$. Then

$\displaystyle\ell(f^{\prime}_{k}\circ\pi^{\prime}_{k}(t))$
$\displaystyle\leq\log\frac{1}{\mu(A_{k}(t))}+1$
$\displaystyle\leq\log\frac{1}{\mu_{k}(A_{k}(t))}+\log\frac{2}{p_{k}}$
$\displaystyle\leq\ell(f_{k}\circ\pi_{k}(t))+\log\frac{2}{p_{k}}.$

Using this in (8) with $\rho_{k}=r^{-k}$, we get (12). ∎

Conversely, any choice of an admissible sequence
$\mathcal{C}=\\{(\pi_{k},f_{k})\\}_{k\geq 1}$ of VLC’s and
$\boldsymbol{p}=(p_{k})_{k\geq 1}$ gives rise to a probability measure

$\displaystyle\mu\propto\sum_{k>0}p_{k}\sum_{s\in\pi_{k}(T)}2^{-\ell(f_{k}(s))}\delta_{s}$

(see, e.g., [5, Sec. 4]), and it is readily verified that, for each $t\in T$
and each $k$,

$\displaystyle\log\frac{1}{\mu(A_{k}(t))}\leq\ell(f_{k}\circ\pi_{k}(t))+\log\frac{1}{p_{k}}.$

Consequently, the machinery developed in this section can be used to give a
self-contained proof of Prop. 1. In fact, using a construction due to Maurer
[5], we can completely eliminate the explicit mminimization over increasing
sequences of partitions, as in Prop. 1–instead, given the choice of
$\mu\in\mathcal{P}(T)$ (or, equivalently, a uniquely decodable code
$f\mathrel{\mathop{\mathchar 58\relax}}T\to\\{0,1\\}^{*}$), the mappings
$\pi_{k}$ and $f_{k}$ at resolution level $r^{-k}$ are chosen so that, for
each $t\in T$, the binary string $f_{k}\circ\pi_{k}(t)$ is obtained by
truncating the lossless representation $f(t)$ to the smallest number of bits,
such the diameter of the set of all $t^{\prime}\in T$ that could be ‘confused’
with $t$ on the basis of this truncated representation is at most $r^{-k}$.
This set is then taken as $A_{k}(t)$. We leave the details to the full version
of this work.

##  IV The lower bound for Gaussian processes

We now consider the case when the process $(X_{t})_{t\in T}$ is Gaussian and
$T$ is endowed with the canonical metric (4). We will use $L,L_{1},\ldots$ to
denote various absolute constants. Note that their values are not necessarily
the same in different appearances. The main technical tool for the lower bound
is the following improvement of Sudakov minoration [1, Prop. 2.4.9]:

######  Proposition 2.

Let $t_{1},\dots,t_{m}\in T$ be such that
$d\left(t_{\ell},t_{\ell^{\prime}}\right)\geq a$ if $\ell\neq\ell^{\prime}$.
Consider $b>0$ and, for each $\ell\leq m$, a finite set $H_{\ell}\subset
B\left(t_{\ell},b\right)$. Then for $H=\bigcup_{\ell\leq m}H_{\ell}$ we have

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in
H}X_{t}\Big{]}\geq\frac{a}{L_{1}}\sqrt{\log m}-L_{2}b\sqrt{\log
m}+\min_{\ell\leq m}\mathbf{E}\Big{[}\sup_{t\in H_{\ell}}X_{t}\Big{]}.$

When $b\leq a/\left(2L_{1}L_{2}\right)$, we have

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in
H}X_{t}\Big{]}\geq\frac{a}{2L_{1}}\sqrt{\log m}+\min_{\ell\leq
m}\mathbf{E}\Big{[}\sup_{t\in H_{\ell}}X_{t}\Big{]}.$

Another ingredient is the construction of an increasing sequence of partitions
on $T$. We follow Bednorz [10] and Talagrand [13] and use a greedy procedure
to construct the partitions $(\mathcal{A}_{k})_{k\geq 0}$ for a fixed $r>1$.
For any $A\subseteq T$, let $G(A)\mathrel{\mathop{\mathchar
58\relax}}=\mathbf{E}[\sup_{t\in A}X_{t}]$. Let $\mathcal{A}_{0}=\\{T\\}$. To
construct $\mathcal{A}_{k}$ for $k\geq 1$ from $\mathcal{A}_{k-1}$, we
partition each $B\in\mathcal{A}_{k-1}$ into sets $A_{1},\ldots,A_{m}$ as
follows: Let $B_{0}\mathrel{\mathop{\mathchar 58\relax}}=B$ and choose
$t_{1}\in B_{0}$ so that

$\displaystyle G(B(t_{1},r^{-k-1}/2)\cap B_{0})=\max_{t\in
B_{0}}G(B(t,r^{-k-1}/2)\cap B_{0}).$

Let $A_{1}\mathrel{\mathop{\mathchar 58\relax}}=B(t_{1},r^{-k}/2)\cap B_{0}$
and $B_{1}\mathrel{\mathop{\mathchar 58\relax}}=B_{0}\setminus A_{1}$. Now
iterate this: If, for $i\geq 1$, $B_{i-1}\neq\varnothing$, choose $t_{i}\in
B_{i-1}$ so that

$\displaystyle G(B(t_{i},r^{-k-1}/2)\cap B_{i-1})$
$\displaystyle\quad=\max_{t\in B_{i-1}}G(B(t,r^{-k-1}/2)\cap B_{i-1}).$

Let $A_{i}\mathrel{\mathop{\mathchar 58\relax}}=B(t_{i},r^{-k}/2)\cap B_{i-1}$
and $B_{i}\mathrel{\mathop{\mathchar 58\relax}}=B_{i-1}\setminus A_{i}$ and
continue. This procedure is guaranteed to terminate for some $m\leq
N(T,d,r^{-k}/2)$, where $N(T,d,\cdot)$ are the covering numbers of $(T,d)$.

We are now ready to state the majorizing measure theorem via codes.

######  Theorem 6.

Let $(X_{t})_{t\in T}$ be a centered Gaussian process. For any
$r\geq\max\\{2,L\\}$, there exists an admissible sequence $\mathcal{C}$ of
VLC’s with $\rho_{k}\leq r^{-k}$, such that

$\displaystyle\mathbf{E}\Big{[}\sup_{t\in
T}X_{t}\Big{]}\gtrsim\frac{1}{r}\sigma_{\mathcal{C}}(t),\qquad\forall\,t\in
T.$ (13)

###### Proof.

Let $L=L_{1}L_{2}$, where $L_{1},L_{2}$ are the contants from Prop. 2. Given
$r\geq L$, let $(\mathcal{A})_{k\geq 0}$ be an increasing sequence of
partitions as described above. For each $k$ and each $A\in\mathcal{A}_{k}$,
pick a unique point $s_{A}\in A$ and then let
$\pi_{k}(t)\mathrel{\mathop{\mathchar 58\relax}}=s_{A_{k}(t)}$, where
$A_{k}(t)$ is the unique element of $\mathcal{A}_{k}$ containing $t$.

We construct the codes $f_{k}$ inductively. Set
$f_{0}(\pi_{0}(t))={\mathsf{e}}$, the empty string in $\\{0,1\\}^{*}$.
Assuming $f_{0},\dots,f_{k-1}$ have been constructed, we assign code lengths
$\ell_{k}(s)$ to the points $s\in\pi_{k}(T)$ and show that this assignment
satisfies the Kraft–McMillan inequality. Thus, there exists a prefix code
$f_{k}\mathrel{\mathop{\mathchar 58\relax}}\pi_{k}(T)\to\\{0,1\\}^{*}$ with
$\ell(f_{k}(s))=\ell_{k}(s)$ for all $s\in\pi_{k}(T)$.

For each $s\in\pi_{k}(T)$, let $i_{k}(s)\in\mathbb{N}$ be the index of the set
$A_{k}(s)\equiv\pi_{k}^{-1}(s)$ as a partition element in
$A_{k-1}(s)\equiv\pi_{k-1}^{-1}(s)$ inherited from the above greedy
construction procedure. Then, with
$\ell_{k}(s)=\ell(f_{k-1}\circ\pi_{k-1}(s))+\log(i_{k}(s)+1)^{2}$, we have

$\displaystyle\sum_{s\in\pi_{k}(T)}2^{-\ell_{k}(s)}$
$\displaystyle=\sum_{t\in\pi_{k-1}(T)}\sum_{s\mathrel{\mathop{\mathchar
58\relax}}\pi_{k-1}(s)=t}2^{-\ell(f_{k-1}(s))-\log(i_{k}(s)+1))^{2}}$
$\displaystyle\leq\sum_{t\in\pi_{k-1}(T)}2^{-\ell(f_{k-1}(t))}\sum_{i\geq
1}\frac{1}{(i+1)^{2}}\leq 1.$

Hence the existence of a uniquely decodable (prefix) code $f_{k}$ is
guaranteed by Kraft–McMillan inequality. Then, by the construction procedure
and Prop. 2, for each $t\in T$,

$\displaystyle G(A_{k-1}(t))\geq
G(A_{k+1}(t))+Lr^{-k}\sqrt{\log(i_{k}(\pi_{k}(t)))}.$

Since $1+\sqrt{\log i}\geq\sqrt{1+\log i}\geq\sqrt{\log(i+1)}$ for $i\geq 1$,

$\displaystyle G(A_{k-1}(t))+Lr^{-k}$ $\displaystyle\geq
G(A_{k+1}(t))+Lr^{-k}\sqrt{\log(i_{k}(\pi_{k}(t))+1)^{2}}$
$\displaystyle=G(A_{k+1}(t))+Lr^{-k}\sqrt{\ell_{k}(t)-\ell_{k-1}(t)},$

where $\ell_{k}(t)=\ell(f_{k}\circ\pi_{k}(t))$. Applying induction on
$G(A_{0}(t))$ and $G(A_{1}(t))$, we obtain

$\displaystyle
G(T)+L\gtrsim\sum_{k}r^{-k}\sqrt{\ell_{k}(t)-\ell_{k-1}(t)},\qquad\forall\,t\in
T$ (14)

Thm. 2 and the fact that $G(T)\gtrsim{\rm diam}(T)$, so that the universal
constant can be absorbed by $G(T)$, give the result. ∎

## Acknowledgments

The authors would like to thank Daniel Roy for pointing out some typos and
inaccuracies in the proof of Theorem 1.

## References

  * [1] M. Talagrand, _Upper and Lower Bounds for Stochastic Processes_. Springer, 2014.
  * [2] X. Fernique, “Regularité des trajectoires des fonctions aléatoires gaussiennes,” in _Ecole d’Eté de Probabilités de Saint-Flour IV—1974_. Springer, 1975, pp. 1–96.
  * [3] M. Talagrand, “Regularity of gaussian processes,” _Acta Mathematica_ , vol. 159, pp. 99–149, 1987.
  * [4] O. Guédon and A. Zvavitch, “Supremum of a process in terms of trees,” in _Geometric Aspects of Functional Analysis_. Springer, 2003, pp. 136–147.
  * [5] A. Maurer, “Majorizing codes and measures,” preprint, available at http://www.andreas-maurer.eu/mmnotes.pdf, 2010.
  * [6] T. M. Cover and J. A. Thomas, _Elements of Information Theory_ , 2nd ed. Wiley, 2006.
  * [7] I. Kontoyiannis and J. Zhang, “Arbitrary source models and Bayesian codebooks in rate-distortion theory,” _IEEE Trans. Inform. Theory_ , vol. 48, no. 8, pp. 2276–2290, August 2002.
  * [8] P. Massart, _Concentration Inequalities and Model Selection_. Springer, 2007.
  * [9] J.-Y. Audibert and O. Bousquet, “Combining PAC-Bayesian and generic chaining bounds,” _Journal of Machine Learning Research_ , vol. 8, no. 32, pp. 863–889, 2007.
  * [10] W. Bednorz, “The majorizing measure approach to sample boundedness,” _Colloquium Mathematicae_ , vol. 139, no. 2, pp. 205–227, 2015.
  * [11] X. Fernique, “Caractérisation de processus à trajectoires majorées ou continues,” _Séminaire de probabilités de Strasbourg_ , vol. 12, pp. 691–706, 1978.
  * [12] R. van Handel, “Probability in high dimension,” Princeton University lecture notes, 2016.
  * [13] M. Talagrand, “A simple proof of the majorizing measure theorem,” _Geometric and Functional Analysis_ , vol. 2, no. 1, pp. 118–125, March 1992\.