# Majorizing Measures, Sequential Complexities, and Online Learning

Adam Block
MIT  Yuval Dagan
MIT  Alexander Rakhlin
MIT

###### Abstract

We introduce the technique of generic chaining and majorizing measures for
controlling sequential Rademacher complexity. We relate majorizing measures to
the notion of fractional covering numbers, which we show to be dominated in
terms of sequential scale-sensitive dimensions in a horizon-independent way,
and, under additional complexity assumptions establish a tight control on
worst-case sequential Rademacher complexity in terms of the integral of
sequential scale-sensitive dimension. Finally, we establish a tight
contraction inequality for worst-case sequential Rademacher complexity. The
above constitutes the resolution of a number of outstanding open problems in
extending the classical theory of empirical processes to the sequential case,
and, in turn, establishes sharp results for online learning.

Keywords: Online learning, Majorizing Measures, Sequential Rademacher
Complexity, Chaining

##  1 Introduction

One of the primary goals of learning theory is to understand how the sample
complexity of learning depends on the complexity of the model. Classically,
much of the research focused on the case where data are drawn independently
from some population distribution. The mismatch between sample and population
inevitably leads to questions of uniform convergence. To answer such
questions, the theory of empirical processes was developed, with seminal
papers establishing non-asymptotic rates of convergence in terms of covering
numbers, chaining (Dudley,, 1973), VC dimension (Vapnik & Chervonenkis,,
1971), and scale-sensitive combinatorial parameters (Bartlett et al. ,, 1996;
Kearns & Schapire,, 1994).

A central notion of complexity is the (empirical) Rademacher complexity (Giné
& Zinn,, 1984), defined for a data set $z_{1},\dots,z_{n}\in{\mathcal{Z}}$ and
a real-valued function class $\mathcal{F}$ on ${\mathcal{Z}}$ as

$\widehat{\mathcal{R}}_{n}(\mathcal{F})=\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{t=1}^{n}\varepsilon_{t}f(z_{t})\right],$
(1)

where $\varepsilon_{t}$ are independent Rademacher random variables. It is a
classical result that $\widehat{\mathcal{R}}_{n}(\mathcal{F})$ determines the
rate of convergence of uniform laws of large numbers over the function class
$\mathcal{F}$. Sharp upper and lower bounds on sample complexity of prediction
and estimation have been established via Rademacher complexity and its
localized versions (Bartlett & Mendelson,, 2002).

Just as important as the introduction of these notions of complexity has been
the development of the relationships among them. In particular, it is a result
of Dudley (Dudley,, 1973) that the Rademacher complexity is controlled by
integrating a function of the covering number and this, in turn, can be
bounded by the integral of the square root of the scale-sensitive
combinatorial dimension, as shown by Mendelson & Vershynin, (2003); Rudelson &
Vershynin, (2006). On the other hand, closely related Gaussian averages,
obtained by replacing Rademacher with Gaussian random variables in (1), are
known to be tightly (up to a constant) controlled via generic chaining and
majorizing measures (Fernique,, 1975; Talagrand,, 1996), and may be strictly
smaller than the bounds provided by Dudley’s chaining technique. It is fair to
say that the foundations of statistical learning when the data are i.i.d. and
presented all at once are fairly well-understood.

In contrast to statistical learning, in online learning the data arrive
sequentially. The learner is tested on the new datum, observes the outcome,
and updates the model with the new information. In the common formulation of
the online learning problem, the sequence as treated as non-stochastic
(individual), or even adaptively and adversarially chosen (Cesa-Bianchi &
Lugosi,, 2006). For online binary classification, the fundamental result of
Littlestone, (1988) (and the agnostic generalization of Ben-David et al. ,
(2009)) characterizes learnability in terms of finiteness of Littlestone
dimension, the counterpart to VC dimension in statistical learning. Motivated
by these results, Rakhlin et al. , (2010) developed sequential analogues of
Rademacher averages, covering numbers, and scale-sensitive dimensions, and
showed that sample complexity of online learning can be related to these
quantities. For example, for online supervised learning with indicator or
absolute value loss, the minimax regret $V_{n}(\mathcal{F})$, defined as the
average loss of an algorithm minus the average prediction loss of the best
model in $\mathcal{F}$, is—up to a multiplicative factor of $2$—equal to the
worst-case sequential Rademacher complexity of $\mathcal{F}$ (Rakhlin et al.
,, 2010), a quantity we shall define below. Furthermore, in parallel to the
close relationship between statistical learning and uniform laws of large
numbers, the sample complexity of online learning can be viewed through the
lens of uniform martingale laws of large numbers (Rakhlin et al. ,, 2015).

In recent years, sequential complexities have been used in an increasing range
of topics, including private learning (Alon et al. ,, 2019; Bun et al. ,,
2020; Jung et al. ,, 2020; Ghazi et al. ,, 2020), adversarial robustness of
sampling streaming data (Alon et al. ,, 2021), denoising in autoregressive
models (Hall et al. ,, 2016; Foster et al. ,, 2020), contextual bandits
(Foster & Rakhlin,, 2020), among others.

While many of the parallels between the classical results in empirical process
theory and their sequential (or martingale) counterparts have been
established, a number of the fundamental relationships and techniques (such as
generic chaining, a sharp contraction principle) are still missing. This paper
addresses some of these gaps.

Before stating our contributions, we define the main object of study,
sequential Rademacher averages. We are primarily interested in certain dyadic
martingales. As before, let $\varepsilon_{1},\ldots,\varepsilon_{n}$ be
independent Rademacher random variables, and let
${\boldsymbol{z}}_{t}(\varepsilon)_{1\leq t\leq n}$ be a predictable process
with respect to the filtration
$\mathcal{A}_{t}=\sigma(\varepsilon_{1},\dots,\varepsilon_{t})$; equivalently,
we can think of ${\boldsymbol{z}}$ as a complete binary tree of depth $n$ with
each vertex ${\boldsymbol{z}}_{t}(\varepsilon)$ labelled by an element of
$\mathcal{Z}$ according to the path $\varepsilon_{1},\dots,\varepsilon_{t-1}$
(see the bottom of this section for complete definitions). Given a real-valued
function class $\mathcal{F}$ on $\mathcal{Z}$, we follow (Rakhlin et al. ,,
2010) and define the sequential Rademacher complexity as

$\mathcal{R}_{n}(\mathcal{F},{\boldsymbol{z}})=\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\frac{1}{n}\sum_{t=1}^{n}\varepsilon_{t}f({\boldsymbol{z}}_{t}(\varepsilon))\right]$
(2)

We note that if ${\boldsymbol{z}}$ is a tree whose labels are constant as a
function of $t$, i.e., ${\boldsymbol{z}}_{t}(\varepsilon)$ is independent of
$\varepsilon$, we recover the classical notion of Rademacher complexity in
(1). Much of (Rakhlin et al. ,, 2010) is devoted to demonstrating that this
is, in some sense, the “correct” extension to the online case and this paper
is primarily concerned with developing upper bounds for this quantity in terms
of various complexity measures of $\mathcal{F}$.

The structure of the paper is given by the order of the following
contributions:

  1. 1.

We introduce a notion of majorizing measure in the online setting and show
that the sequential Rademacher complexity is bounded:

$\mathcal{R}_{n}(\mathcal{F},{\boldsymbol{z}})~{}\lesssim~{}\inf_{\operatorname{supp}\mu\subseteq\mathcal{F}({\boldsymbol{z}})}\sup_{\begin{subarray}{c}{\boldsymbol{v}}\in\mathcal{F}({\boldsymbol{z}})\\\
\varepsilon\in\\{\pm
1\\}^{n}\end{subarray}}\frac{1}{\sqrt{n}}\int_{0}^{1}\sqrt{\log\frac{1}{\mu(B_{\delta}({\boldsymbol{v}},\varepsilon))}}d\delta$
(3)

The upper bound can be viewed as an analogue of the corresponding upper bound
via majorizing measures (Fernique,, 1975; Talagrand,, 1996). In proving the
above, we introduce a new concentration inequality for martingales.

  2. 2.

We extend the notion of fractional cover introduced by Alon et al. , (2021) to
real-valued function classes and show that this notion of complexity controls
the upper bound given by a majorizing measure.

  3. 3.

We prove a sequential analogue of the results of Mendelson & Vershynin, (2003)
for fractional covers, showing that

$N^{\prime}(\mathcal{F},\delta)~{}\lesssim~{}\left(\frac{C}{\delta}\right)^{\mathsf{fat}_{c\delta}(\mathcal{F})}$
(4)

thereby resolving an open question raised in (Rakhlin et al. ,, 2015). Here
$\mathsf{fat}$ is a sequential scale-sensitive dimension, defined below.

  4. 4.

We prove a sequential analogue of the results of Rudelson & Vershynin, (2006),
showing that

$\mathcal{R}_{n}(\mathcal{F})~{}\lesssim~{}\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta$
(5)

where
$\mathcal{R}_{n}(\mathcal{F})=\sup_{{\boldsymbol{z}}}\mathcal{R}_{n}(\mathcal{F},{\boldsymbol{z}})$
is the worst-case Rademacher complexity over all trees ${\boldsymbol{z}}$. For
sufficiently simple classes $\mathcal{F}$, we show that this inequality can be
reversed and apply the result to prove a dimension-independent contraction
inequality for sequential Rademacher complexity, thereby resolving another
open problem from (Rakhlin et al. ,, 2015).

### Notation.

Bold lower-case letters will denote complete binary trees. Given a depth $n$
binary tree ${\boldsymbol{v}}$, denote by $\varepsilon\in\\{\pm 1\\}^{n}$ a
path from the root to a leaf of the tree, where $\varepsilon_{t}=-1$ signifies
that node $t+1$ of the path is the left child of node $t$. A _real-valued
tree_ is a tree labelled by real numbers. If
${\boldsymbol{v}},{\boldsymbol{v}}^{\prime}$ are real-valued trees, define by
${\boldsymbol{v}}(\varepsilon)=({\boldsymbol{v}}_{1}(\varepsilon),\dots,{\boldsymbol{v}}_{n}(\varepsilon))$
the values of ${\boldsymbol{v}}$ on the path $\varepsilon$, and let

$\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|^{2}=\sum_{t=1}^{n}\left({\boldsymbol{v}}_{t}(\varepsilon)-{\boldsymbol{v}}_{t}^{\prime}(\varepsilon)\right)^{2}.$
(6)

Given a real-valued tree ${\boldsymbol{v}}$, we let
$\mathbb{T}_{\boldsymbol{v}}$ be the associated tree process, the random
variable

$\mathbb{T}_{\boldsymbol{v}}(\varepsilon)=\sum_{t=1}^{n}\varepsilon_{t}{\boldsymbol{v}}_{t}(\varepsilon).$
(7)

If ${\boldsymbol{z}}$ is a $\mathcal{Z}$-valued tree that is clear from
context and $f$ is a real-valued function on $\mathcal{Z}$, we often
abbreviate $\mathbb{T}_{f}=\mathbb{T}_{f({\boldsymbol{z}})}$ and write
$\mathcal{F}({\boldsymbol{z}})=\\{f\circ{\boldsymbol{z}}:f\in\mathcal{F}\\}$.
For two quantities $a,b$, we say that $a\lesssim b$ if there exists a
universal constant $C$, independent of the quantities that determine $a,b$,
such that $a\leq Cb$.

##  2 Majorizing Measures and Upper Bounds

In the classical setting, one of the most fundamental quantities that controls
the size of the supremum of a stochastic process is the covering number of the
underlying index set, i.e., the minimal number of points such that every
member of the index set is within $\delta$ of one of the chosen points. In
(Rakhlin et al. ,, 2015), this definition is extended to the sequential
setting:

######  Definition 1.

Let ${\boldsymbol{z}}$ be a $\mathcal{Z}$-valued tree of depth $n$ and let
$\mathcal{F}\subset\mathbb{R}^{\mathcal{Z}}$. A covering at scale $\delta$ is
a set of binary real-valued trees
${\boldsymbol{v}}^{1},\cdots,{\boldsymbol{v}}^{N}$ such that for all
$f\in\mathcal{F}$ and all $\varepsilon\in\\{\pm 1\\}^{n}$, there is some $j$
such that

$\left|\left|f({\boldsymbol{z}}(\varepsilon))-{\boldsymbol{v}}^{j}(\varepsilon)\right|\right|^{2}\leq
n\delta^{2}.$ (8)

The covering number $N(\mathcal{F},\delta,{\boldsymbol{z}})$ of a class
$\mathcal{F}$ for a tree ${\boldsymbol{z}}$ at scale $\delta$ is the minimal
$N$ such that there exists a $\delta$-covering of size $N$.

As noted in (Rakhlin & Sridharan,, 2015; Rakhlin et al. ,, 2010), we can
recover the classical definition by restricting to trees ${\boldsymbol{z}}$,
whose values are path-independent. In analogy with the statistical learning
regime, we may apply the chaining technique to bound the sequential Rademacher
complexity in terms of these covering numbers; in fact, for uniformly bounded
function classes, (Rakhlin et al. ,, 2015, Theorem 3) guarantees

$\mathcal{R}_{n}(\mathcal{F},{\boldsymbol{z}})~{}\lesssim~{}\inf_{\alpha>0}\left(\alpha+\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\log
N(\mathcal{F},\delta,{\boldsymbol{z}})}d\delta\right).$ (9)

Looking back to the classical case, we note that the generic chaining and
majorizing measure approaches (Talagrand,, 2014, 1996; Fernique,, 1975) would
suggest that the bound in (9) is not tight in all cases. In the classical
setting, generic chaining approaches give significant improvements over the
Dudley entropy integral, as can be seen, for example, from the case of
ellipsoids in Hilbert space (Talagrand,, 2014, Sec 2.5). Such improvements go
well beyond logarithmic factors. Furthermore, Rakhlin et al. , (2015) note
that a clean, $n$-independent upper bound for the sequential covering number
in terms of the sequential scale-sensitive dimension in the style of
(Mendelson & Vershynin,, 2003) is not yet known, resulting in additional
looseness when using (9).

We now introduce a generalization of majorizing measures to the sequential
case.

######  Definition 2.

For a collection of $[0,1]$-valued binary trees $\mathcal{V}$ of depth $n$,
for ${\boldsymbol{v}}\in\mathcal{V}$ and for a fixed path $\varepsilon$, let
$B_{\delta}({\boldsymbol{v}},\varepsilon)$ be the set of trees
${\boldsymbol{v}}^{\prime}$ in $\mathcal{V}$ such that
$\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|^{2}\leq
n\delta^{2}$. For a measure $\mu$ on the set of $[0,1]$-valued trees of depth
$n$, and $0\leq\alpha\leq 1$, let

$I_{\mu}^{\alpha}({\boldsymbol{v}},\varepsilon)=\alpha+\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\log\frac{1}{\mu(B_{\delta}({\boldsymbol{v}},\varepsilon))}}d\delta.$
(10)

We let

$\displaystyle
I_{\mu}^{\alpha}=\sup_{\begin{subarray}{c}{\boldsymbol{v}}\in\mathcal{V}\\\
\varepsilon\in\\{\pm
1\\}^{n}\end{subarray}}I_{\mu}^{\alpha}({\boldsymbol{v}},\varepsilon)$
$\displaystyle
I_{\mathcal{F},{\boldsymbol{z}}}^{\alpha}=\inf_{\operatorname{supp}\mu\subseteq\mathcal{F}({\boldsymbol{z}})}I_{\mu}^{\alpha}$
$\displaystyle
I_{\mathcal{F}}^{\alpha}=\sup_{\boldsymbol{z}}I^{\alpha}_{\mathcal{F},{\boldsymbol{z}}}$
(11)

To see that this definition extends the classical one, consider the special
case where $\mathcal{V}$ is restricted to contain only trees that are constant
on vertices of equal depth, corresponding to the batch setting; thus, the path
$\varepsilon$ in the above definition becomes irrelevant and we recover the
classical notion of a majorizing measure (Talagrand,, 2014, p. 177). This
notion of complexity is not very useful unless it actually controls the size
of our stochastic process; fortunately, we have:

######  Theorem 3.

Let $\mathcal{F}$ be a separable $[0,1]$-valued function class on
$\mathcal{Z}$. Let ${\boldsymbol{z}}$ be a $\mathcal{Z}$-valued binary tree of
depth $n$. Then with probability at least $1-\rho$ over $\varepsilon$ and for
any $\alpha\geq 0$

$\sup_{f\in\mathcal{F}}\left(\frac{1}{n}\mathbb{T}_{f({\boldsymbol{z}})}(\varepsilon)\right)~{}\lesssim~{}I_{\mathcal{F},{\boldsymbol{z}}}^{\alpha}+\sqrt{\frac{\log\frac{1}{\rho}}{n}}$
(12)

In particular, the sequential Rademacher complexity is bounded by

$\mathcal{R}_{n}(\mathcal{F},{\boldsymbol{z}})~{}\lesssim~{}\inf_{\alpha>0}\left(\alpha+\inf_{\operatorname{supp}\mu\subset\mathcal{F}({\boldsymbol{z}})}\sup_{\begin{subarray}{c}{\boldsymbol{v}}\in\mathcal{F}({\boldsymbol{z}})\\\
\varepsilon\in\\{\pm
1\\}^{n}\end{subarray}}\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\log\frac{1}{\mu(B_{\delta}({\boldsymbol{v}},\varepsilon))}}d\delta\right)$
(13)

The proof of Theorem 3 is somewhat technical and thus deferred to Appendix A.
The proof rests on the following new martingale concentration inequality that
can be viewed as a stronger version of (Bartlett et al. ,, 2008, Lemma 2):

######  Lemma 4.

Let ${\boldsymbol{v}}$ be a $[-1,1]$-labelled binary tree of depth $n$ and
$\varepsilon_{1},\dots,\varepsilon_{n}$ independent Rademacher variables. Then
there is a constant $C$ such that with probability at least $1-\rho$ over the
$\varepsilon_{t}$,

$\frac{\left|\sum_{t=1}^{n}\varepsilon_{t}{\boldsymbol{v}}_{t}(\varepsilon)\right|}{\left|\left|{\boldsymbol{v}}(\varepsilon)\right|\right|\sqrt{\log\frac{1}{\rho}+\log\log\frac{e\sqrt{n}}{\left|\left|{\boldsymbol{v}}(\varepsilon)\right|\right|}}}\leq
C$ (14)

For the probabilist, an equivalent rephrasing of Lemma 4 is to let $M_{t}$ be
a martingale sequence whose differences are conditionally symmetric and
bounded in absolute value by $1$. Let $[M]_{t}$ be its quadratic variation
process. Then the above says that with high probability,

$\frac{\left|M_{n}\right|}{\sqrt{[M]_{n}\left(\log\frac{1}{\rho}+\log\log\frac{en}{[M]_{n}}\right)}}\lesssim
1$ (15)

One way of thinking about this is to consider it as a non-asymptotic version
of the martingale Laws of the Iterated Logarithm proved in (de la Peña,, 1999;
Bercu & Touati,, 2008).

Much like the classical case, structural results of the function class can
help control the majorizing measure’s upper bound. One example of such a
result concerns Lipschitz compositions:

######  Proposition 5.

Let $\mathcal{F}\subseteq[0,1]^{\mathcal{Z}}$ and let $\ell:[0,1]\to[0,1]$ be
$L$-Lipschitz. Then $I_{\ell\circ\mathcal{F},{\boldsymbol{z}}}^{\alpha}\leq
LI_{\mathcal{F},{\boldsymbol{z}}}^{\alpha}$.

While majorizing measures in the classical case fully characterize the
associated Gaussian process, constructing these multi-scale measures for a
given class of functions at hand is notoriously difficult. In the following
section, inspired by (Alon et al. ,, 2021) for the binary-valued case, we
introduce a single-scale measure that is easier to analyze than the multi-
scale construction.

##  3 Fractional Covers

As we just remarked, the multi-scale nature of the majorizing measure makes it
difficult to apply the technique to practical function classes. Thus we
introduce the fractional covering number for real-valued function classes as a
single-scale alternative:

######  Definition 6.

Let ${\boldsymbol{z}}$ a binary, $\mathcal{Z}$-valued tree of depth $n$ and
let $\mathcal{F}\subset\mathbb{R}^{\mathcal{Z}}$. A measure $\mu$ on the space
of binary real-valued trees of depth $n$ is a fractional covering at scale
$\delta$ of size $\gamma$ if for all $f\in\mathcal{F}$ and
$\varepsilon\in\\{\pm 1\\}^{n}$, we have

$\mu\left(\left\\{{\boldsymbol{v}}:\left|\left|{\boldsymbol{v}}(\varepsilon)-f({\boldsymbol{z}}(\varepsilon))\right|\right|^{2}\leq
n\delta^{2}\right\\}\right)\geq\frac{1}{\gamma}.$ (16)

The fractional covering number
$N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})$ of $\mathcal{F}$ at scale
$\delta$ is the smallest $\gamma$ such that there exists a fractional cover of
$\mathcal{F}$ at scale $\delta$ of size $\gamma$. Let
$N^{\prime}(\mathcal{F},\delta)=\sup_{\boldsymbol{z}}N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})$.

We see immediately (and prove in Appendix D) that this new notion of size is
controlled by the sequential covering number introduced in (Rakhlin et al. ,,
2010):

######  Lemma 7.

For any ${\boldsymbol{z}},\mathcal{F},\delta$, we have
$N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})\leq
N(\mathcal{F},\delta,{\boldsymbol{z}})$.

Interestingly, at least in the classical case, the reverse inequality holds as
well:

######  Lemma 8.

Let ${\boldsymbol{z}}$ be a tree whose labels are constant as a function of
depth. Then $N\left(\mathcal{F},2\delta,{\boldsymbol{z}}\right)\leq
N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})\leq
N(\mathcal{F},\delta,{\boldsymbol{z}})$.

The proof of Lemma 8 is deferred to Appendix D. Thus, at least in the
classical case, the fractional covering number does not provide any
improvement over the classical notion of covering number; whether such a
result holds in the sequential case remains open, due to the lack of packing-
covering duality in this setting.

To understand the connection between fractional covers and majorizing
measures, we note that Definition 6 can be rephrased to say that
$\mu_{\delta}$ is a $\delta$-fractional cover of size $\gamma$ if

$\sup_{\begin{subarray}{c}f\in\mathcal{F}\\\ \varepsilon\in\\{\pm
1\\}^{n}\end{subarray}}\log\frac{1}{\mu_{\delta}\left(B_{\delta}(f({\boldsymbol{z}}),\varepsilon)\right)}=\log\gamma.$
(17)

Applying Theorem 3 and setting $\alpha=0$ for ease of exposition, we see that,
after putting the supremum inside of the integral,

$\displaystyle\mathbb{E}\left[\sup_{f\in\mathcal{F}}\mathbb{T}_{f}(\varepsilon)\right]$
$\displaystyle\lesssim\sqrt{n}\sup_{\begin{subarray}{c}f\in\mathcal{F}\\\
\varepsilon\in\left\\{\pm
1\right\\}^{n}\end{subarray}}\int_{0}^{1}\sqrt{\log\frac{1}{\mu(B_{\delta}(f({\boldsymbol{z}}),\varepsilon)}}d\delta$
(18)
$\displaystyle\leq\sqrt{n}\int_{0}^{1}\sup_{\begin{subarray}{c}f\in\mathcal{F}\\\
\varepsilon\in\left\\{\pm
1\right\\}^{n}\end{subarray}}\sqrt{\log\frac{1}{\mu(B_{\delta}(f({\boldsymbol{z}}),\varepsilon))}}d\delta$
(19)

for all measures $\mu$. The last integrand above _almost_ looks like the left-
hand side of (17) and so we might hope that we can replace this integrand with
$\sqrt{\log N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})}$. The problem
with this last step is that the measure $\mu_{\delta}$ of the fractional cover
is allowed to depend on the scale while the majorizing measure is not; thus it
is not obvious that a chaining bound with fractional covers follows from
Theorem 3. Fortunately, as the following proposition demonstrates, we are
still able to control the majorizing measure by fractional covers and thus the
above critique does not apply:

######  Proposition 9.

Let ${\boldsymbol{z}}$ be a $\mathcal{Z}$-valued binary tree of depth $n$ and
let $\mathcal{F}$ be a class of real-valued functions on $\mathcal{Z}$. Then

$I_{\mathcal{F},{\boldsymbol{z}}}^{\alpha}~{}\lesssim~{}\alpha+\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\log
N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})}d\delta$ (20)

In other words, fractional covers dominate majorizing measures, up to a
constant.

A proof of Proposition 9 can be found in Appendix D. An immediate corollary of
the above, which follows from combining Theorem 3 and Proposition 9 is

######  Corollary 10.

Let $\mathcal{F}$ be a separable $[0,1]$-valued function class on
$\mathcal{Z}$. Let ${\boldsymbol{z}}$ be a $\mathcal{Z}$-valued binary tree of
depth $n$. Let $N^{\prime}(\mathcal{F},\delta)$ be the fractional covering
number at scale $\delta$. Then with probability at least $1-\rho$ over
$\varepsilon$, for all $\alpha\geq 0$,

$\sup_{f\in\mathcal{F}}\left(\frac{1}{n}\mathbb{T}_{f({\boldsymbol{z}})}(\varepsilon)\right)~{}\lesssim~{}\alpha+\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\log
N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})}d\delta+\sqrt{\frac{\log\frac{1}{\rho}}{n}}.$
(21)

In particular, the sequential Rademacher complexity is bounded by the Dudley
integral:

$\mathcal{R}_{n}(\mathcal{F},{\boldsymbol{z}})~{}\lesssim~{}\inf_{\alpha>0}\left(\alpha+\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\log
N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})}d\delta\right).$ (22)

If we apply Lemma 7 to Corollary 10, we recover the chaining bound with
respect to sequential non-fractional covers of (Rakhlin et al. ,, 2015). As a
first application of our results, using the techniques of Rakhlin et al. ,
(2015) we get a high-probability uniform deviations bound:

######  Corollary 11.

Let $Z_{1},\dots,Z_{t},\dots$ be a sequence of $\mathcal{Z}$-valued random
variables adapted to a filtration $\mathcal{A}_{t}$ and let $\mathcal{F}$ be a
$[0,1]$-valued function class on $\mathcal{Z}$. Then with probability at least
$1-4\rho$,

$\displaystyle\sup_{f\in\mathcal{F}}\left|\frac{1}{n}\sum_{t=1}^{n}f(Z_{t})-\mathbb{E}[f(Z_{t})|\mathcal{A}_{t}]\right|$
$\displaystyle~{}\lesssim~{}\inf_{\alpha>0}I_{\mathcal{F}}^{\alpha}+\sqrt{\frac{\log\frac{1}{\rho}}{n}}$
(23)
$\displaystyle~{}\lesssim~{}\inf_{\alpha>0}\left(\alpha+\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\log
N^{\prime}(\mathcal{F},\delta)}d\delta\right)+\sqrt{\frac{\log\frac{1}{\rho}}{n}}$
(24)

Corollary 11 significantly improves on the results of (Rakhlin et al. ,, 2015,
Section 7) in two ways: first, we chain with respect majorizing measures and
fractional covering numbers which are guaranteed to be at least as good as
sequential covering numbers by Lemma 7; second, our bound removes an
extraneous factor polynomial in $\log n$ and now matches the form of uniform
concentration bounds from the classical regime. In the following section, we
show how combinatorial properties of $\mathcal{F}$ can help us bound
fractional covering numbers.

##  4 Fractional Covering and Fat-Shattering Dimension

Thus far, we have been focused on somewhat abstract results, providing upper
bounds on stochastic processes in terms of majorizing measures and fractional
covering numbers without any evidence that these new quantities improve on the
sequential covering numbers introduced in Rakhlin et al. , (2010); here, we
rectify that and focus on how to control the fractional covering numbers with
combinatorial and structural properties of the function class.

One of the cornerstones in classical learning theory was the development of
Vapnik-Chernovenkis theory and how it relates to uniform convergence over a
binary-valued function class (Vapnik & Chervonenkis,, 1981). This theory was
then extended to real-valued functions with the development of fat-shattering
or scale-sensitive dimension (Bartlett et al. ,, 1996; Kearns & Schapire,,
1994). In the online world, Littlestone, (1988) introduced an analogue of the
VC dimension and Rakhlin et al. , (2015) extended this definition to a
sequential notion of the fat-shattering dimension. Here, we recall the
definition of the fat-shattering dimension and then use it to bound the
fractional covering numbers independently of $n$ in a sequential analogue of
the results of Mendelson & Vershynin, (2003). We then show that, when
integrated in the chaining upper bound of Corollary 10, we can further improve
the bound and provide a sequential analogue of the results of Rudelson &
Vershynin, (2006), which is tight in the Donsker case. Finally, we apply these
results to prove a tight (up to constants) Lipschitz contraction bound on
worst-case Rademacher complexity, improving on the structural results of
Rakhlin et al. , (2015).

We begin by recalling the fat-shattering dimension from (Rakhlin et al. ,,
2015, Definition 7):

######  Definition 12.

Let ${\boldsymbol{z}}$ a $\mathcal{Z}$-labelled binary tree of depth $n$ and
let $\mathcal{F}$ a real-valued function class. We say that $\mathcal{F}$ is
shattered by ${\boldsymbol{z}}$ at scale $\delta$ if there exists a real-
valued binary tree $\mathbf{s}$ such that for all $\varepsilon\in\\{\pm
1\\}^{n}$, there exists an $f\in\mathcal{F}$ such that for all $1\leq t\leq
n$,

$\varepsilon_{t}\left(f({\boldsymbol{z}}_{t}(\varepsilon))-\mathbf{s}_{t}(\varepsilon)\right)\geq\frac{\delta}{2}.$
(25)

The (sequential) fat-shattering dimension $\mathsf{fat}_{\delta}(\mathcal{F})$
is the maximal $n$ such that there exists a tree ${\boldsymbol{z}}$ of depth
$n$ that shatters $\mathcal{F}$ at scale $\delta$.

A sequential version of the Sauer-Shelah lemma was also proven in Rakhlin et
al. , (2015) and this was used to bound the $\ell^{\infty}$ sequential
covering numbers by the fat shattering dimension. In particular, (Rakhlin et
al. ,, 2015, Corollary 1) tells us that if $\mathcal{F}$ takes values in
$[0,1]$ then for any tree ${\boldsymbol{z}}$ of depth $n$,

$N(\mathcal{F},\delta,{\boldsymbol{z}})\leq
N_{\infty}(\mathcal{F},\delta,{\boldsymbol{z}})\leq\left(\frac{2en}{\delta}\right)^{\mathsf{fat}_{\delta}(\mathcal{F})}$
(26)

where $N_{\infty}$ denotes the covering number with respect to
$\ell^{\infty}$. As noted _in situ_ , this method cannot provide
$n$-independent covering number bounds for the $\ell^{2}$ regime because the
$\ell^{\infty}$ covering numbers cannot be independent of dimension in
general. In the classical setting, Dudley extraction, pioneered in Dudley,
(1973), allows for dimension-independent bounds, but, due to the lack of
covering-packing duality in the sequential case, this method cannot be applied
in the online regime. A major advantage of the fractional covering number is
that we are able to eliminate the dependence on $n$ and control the
_fractional_ covering numbers by the fat-shattering dimension. We have the
following bound:

######  Theorem 13.

Let $\mathcal{F}:\mathcal{Z}\to[0,1]$ be a function class. There exist
universal constants $C,c$ such that for all $\delta>0$, and all trees
${\boldsymbol{z}}$

$N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})\leq\left(\frac{C}{\delta}\right)^{3\mathsf{fat}_{c\delta}(\mathcal{F})}$
(27)

The details of the proof of Theorem 13 can be found in Appendix B, but we
provide a sketch here.

We follow Rakhlin et al. , (2015) and discretize the unit interval into sub-
intervals of length proportional to $\delta$; this discretization transforms
the real-valued function class $\mathcal{F}$ into one that takes on finitely
many values. Using this transformation, it suffices to bound the fractional
covering number of a simpler class of functions
$\mathcal{F}:\mathcal{Z}\to\\{0,1,\dots,m\\}$ by
$\mathsf{fat}_{2}(\mathcal{F})$, i.e., it suffices to prove

######  Proposition 14.

Suppose that $\mathcal{F}:\mathcal{Z}\to\mathcal{Y}=\\{0,1,\dots,m\\}$ and
that $\mathsf{fat}_{2}(\mathcal{F})=d$. Then there is a universal constant $C$
such that
$N^{\prime}\left(\mathcal{F},\frac{2}{3},{\boldsymbol{z}}\right)\leq\left(Cm\right)^{3d}$.

We provide full details in Appendix B, but provide a sketch here:

###### Sketch.

We fix the tree ${\boldsymbol{z}}$ and construct the fractional cover
recursively. The idea of the construction is to partition the function class
$\mathcal{F}$ into sub-classes $\mathcal{F}_{j}$ taking the value $j$ on the
root. Lemma 23, proved in Appendix B, tells us that there are at most two such
sub-classes such that
$\mathsf{fat}_{2}(\mathcal{F}_{j})=\mathsf{fat}_{2}(\mathcal{F}_{j^{\prime}})=\mathsf{fat}_{2}(\mathcal{F})$
and that $\left|j-j^{\prime}\right|\leq 1$. Let $j^{*}$ be the minimal $j$
such that $\mathsf{fat}_{2}(\mathcal{F}_{j})=\mathsf{fat}_{2}(\mathcal{F})$
and notice that $j^{*}$ and $j^{*}+1$ are potentially the only values of $j$
such that $\mathsf{fat}_{2}(\mathcal{F}_{j})=\mathsf{fat}_{2}(\mathcal{F})$.
We construct the fractional cover $\mu$ recursively as the following mixture:
with probability $1-p$, where $p$ is a small number to be specified, we label
the root as $j^{*}+1/2$ and label the two subtrees of the root independently,
using the fractional cover with respect to the complete class $\mathcal{F}$.
Otherwise, with probability $p$, we draw a uniformly random
$j\in\\{0,\dots,m\\}\setminus\\{j^{*},j^{*}+1\\}$, label the root as $j$ and
each of the two subtrees independently from the fractional covers with respect
to the subclass $\mathcal{F}_{j}$, which satisfies
$\mathsf{fat}_{2}(\mathcal{F}_{j})\leq\mathsf{fat}_{2}(\mathcal{F})-1$. An
induction proof relying on the recursive construction, found in Appendix B as
Lemma 24, then tells us that if $\mathsf{fat}_{2}(\mathcal{F})\leq d$ and
$\mu$ is as constructed above, then for any integer $k$,

$\inf_{\begin{subarray}{c}f\in\mathcal{F}\\\ \varepsilon\in\\{\pm
1\\}^{n}\end{subarray}}\mu\left(\left\\{{\boldsymbol{v}}|\sum_{t=0}^{n}\mathbf{1}_{\left|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}(_{t}\varepsilon))\right|\geq
1}\leq
k\right\\}\right)\geq(1-p)^{n+1+k}\left(\frac{p}{m}\right)^{d}\binom{k+d}{d}\enspace.$
(28)

Setting $k=\delta n$, $p=\frac{d}{n}$, the right hand side is at least
$(c\delta/m)^{d}$. By the construction, if
$\left|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))\right|<1$
then it is at most $\frac{1}{2}$ and otherwise,
$\left|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))\right|\leq
m$. Thus if ${\boldsymbol{v}}$ is in the above set, then
$\left|\left|{\boldsymbol{v}}(\varepsilon)-f({\boldsymbol{z}}(\varepsilon))\right|\right|^{2}\leq
m^{2}\delta n+\frac{1}{4}(1-\delta)n$. Thus if $\delta\leq\frac{7}{36m^{2}}$,
the result follows by the definition of a fractional cover. ∎

Note that Proposition 14 is already a major improvement over (Rakhlin et al.
,, 2015, Corollary 1), the analogue for non-fractional sequential covers; in
addition, our result matches the form of the classical counterpart, proven in
Mendelson & Vershynin, (2003). Interestingly, the proof of Proposition 14
relies on the independence of sub-trees inherent to the online case; thus, the
same proof does _not_ apply to the classical analogue, proven by use of Dudley
extraction. The key lemma, Lemma 23, very much takes advantage of the
sequential setting and thus the Proposition 14 and consequently Theorem 13,
provide important examples of results that are proved more easily in the
sequential case than in the classical setting. An interesting future direction
would be to extend the proof method to the classical regime and reprove the
analogue of Theorem 13 without the use of Dudley extraction.

If we plug the result of Theorem 13 into that of Corollary 10, we are able to
bound the sequential Rademacher complexity as follows:

$\mathcal{R}_{n}(\mathcal{F})=\sup_{\mathsf{depth}({\boldsymbol{z}})=n}\mathcal{R}_{n}(\mathcal{F},{\boldsymbol{z}})~{}\lesssim~{}\frac{1}{\sqrt{n}}\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})\log\frac{1}{\delta}}d\delta$
(29)

where we take $\alpha=0$ in Corollary 10 for the sake of simplicity of
exposition. Equation (29) improves the results of Rakhlin et al. , (2015) in
that it shaves off a factor polynomial in $\log n$, but we might hope for an
even better bound that removes the $\log\frac{1}{\delta}$ factor. In the
classical regime, it was shown in Rudelson & Vershynin, (2006) that this is
indeed possible and that

$\mathcal{R}_{n}(\mathcal{F})~{}\lesssim~{}\frac{1}{\sqrt{n}}\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta$
(30)

where just in (30), the Rademacher complexity and fat shattering dimension are
the classical notions rather than the sequential notions. In fact, we do get a
sequential analogue to (30) and the proof is much simpler than that in the
classical regime. We have:

######  Proposition 15.

Let $\mathcal{F}$ be a class of functions from $\mathcal{Z}$ to $[0,1]$. Then
for all $b>0$,

$\int_{b}^{1}\sqrt{\log
N^{\prime}(\mathcal{F},\delta)}d\delta~{}\lesssim~{}\int_{cb}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta.$
(31)

As main step in this proof, we bound the fractional covering numbers with
respect to multiple fat numbers:

######  Proposition 16.

There exist universal constants $c,C>0$ such that the following holds: Let
$\mathcal{F}$ be a class of functions from $\mathcal{Z}$ to
$\mathcal{Y}=[0,1]$. Then for all $\delta>0$,

$N^{\prime}(\mathcal{F},\delta)\leq\prod_{i=1}^{\infty}C^{i\cdot\mathsf{fat}_{c\cdot
2^{i}\delta}(\mathcal{F})}$ (32)

###### sketch.

Similarly to the proof of Theorem 13, by discretizing $[0,1]$ into sub-
intervals of length $\approx\delta$, it suffices for us to prove the
following: if $\mathcal{F}$ is a $\\{0,\dots,m\\}$-valued function class, then

$N^{\prime}(\mathcal{F},2)\leq\prod_{i=1}^{\log
m}C^{i\mathsf{fat}_{2^{i}}(\mathcal{F})}.$

To prove the above statement, we construct a fractional cover $\mu$
recursively, in the same spirit as the proof of Proposition 14. Partition
$\mathcal{F}$ into sub-classes $\mathcal{F}_{j}$ taking the value $j$ on the
root, and Lemma 23 tells us that there are at most $2^{i}$ classes $j$ with
$\mathsf{fat}_{2^{i}}(\mathcal{F}_{j})=\mathsf{fat}_{2^{i}}(\mathcal{F})$ and
any two such classes $j,j^{\prime}$ satisfy $|j-j^{\prime}|<2^{i}$. Define by
$i(j)$ as the maximal integer $i$ such that
$\mathsf{fat}_{2^{i}}(\mathcal{F}_{j})<\mathsf{fat}_{2^{i}}(\mathcal{F})$, and
let $j^{*}$ be any minimizer of $i(j)$. Intuitively, $\mathcal{F}_{j^{*}}$ has
the same high-scale fat numbers as $\mathcal{F}$. The fractional cover is
defined as the mixture that labels the root as $j^{*}$ with probability $1-p$
for a small $0<p<1$ and for any other $j$, with probability $p\cdot
4^{-i(j)-1}$. The remainder of the tree is recursively drawn, as in
Proposition 14. By an inductive formula, we derive that for any numbers
$k_{1},k_{2},\dots,k_{\log m}$ and any bounds $d_{1},\dots,d_{\log m}$ on the
fat numbers $\mathsf{fat}_{2^{1}}(\mathcal{F}),\dots,\mathsf{fat}_{2^{\log
m}}(\mathcal{F})$, the fractional cover $\mu$ satisfies

$\inf_{\begin{subarray}{c}f\in\mathcal{F}\\\ \varepsilon\in\\{\pm
1\\}^{n}\end{subarray}}\mu\left(\left\\{{\boldsymbol{v}}\colon\forall
i=1,\dots,\log_{2}m,\sum_{t=0}^{n}\mathbf{1}_{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
2^{i}}|\leq\sum_{i^{\prime}=i}^{\log_{2}m}k_{i^{\prime}}\right\\}\right)\\\
\geq(1-p)^{n+1}\prod_{i=1}^{\log_{2}m}(1-p)^{k_{i}}\left(\frac{p}{4^{i+1}}\right)^{d_{i}}\binom{k_{i}+d_{i}}{d_{i}}.$
(33)

Substituting $k_{i}=8^{-i}n$, we obtain that any ${\boldsymbol{v}}$ in the
above set satisfies
$\|{\boldsymbol{v}}(\varepsilon)-f({\boldsymbol{z}}(\varepsilon))\|\leq O(1)$.
Bounding the binomial coefficients similarly to Proposition 14, the proof
concludes, as we derive a lower bound on the fraction of trees close to
$f({\boldsymbol{z}})$ on any path $\varepsilon$. ∎

While admittedly still somewhat technical, we observe that the proof of
Proposition 15, appearing in Appendix C, is actually significantly easier than
that required for the analogous result in the classical regime, appearing in
(Rudelson & Vershynin,, 2006).

Miraculously, for function classes $\mathcal{F}$ that are not too complex,
Proposition 15 gives a tight bound on the worst-case sequential Rademacher
complexity, up to constants. In order to state such a result, we need to
define what it means for a function class to be simple.

######  Definition 17.

For a constant $c>0$ and $0\leq p<2$, we say that a function class is
$(c,p)$-bounded if for all $0<\delta<1$,

$\mathsf{fat}_{\delta}(\mathcal{F})\leq c\delta^{-p}.$ (34)

We note that many practical function classes are $(c,p)$-bounded; for example,
Littlestone classes satisfy the above for $c=\mathsf{Ldim}(\mathcal{F})$ and
$p=0$. We have the following corollary:

######  Corollary 18.

Let $\mathcal{F}$ be a $(c,p)$-bounded class of functions. Then

$\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta~{}\lesssim~{}\sqrt{n}\mathcal{R}_{n}(\mathcal{F})~{}\lesssim~{}\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta$
(35)

where the constants depend on $\mathcal{F}$ only through $c,p$. The upper
bound holds with no restriction on the complexity of the class $\mathcal{F}$.

Thus for many classes of interest, we have a tight characterization of
sequential Rademacher complexity, matching the characterization in the offline
case. A challenging open problem remains, however: in the classical setting,
majorizing measures provide both an upper and lower bound on the supremum of a
Gaussian process. While our results can be extended to give an upper bound for
the sequential Gaussian complexity, where the path is determined by the signs
of independent Gaussian multipliers, the lower bound remains to be shown.

As an application of our results, we prove a tight Lipschitz contraction
statement for worst-case Rademacher complexity in the $(c,p)$-bounded regime
that is dimension-independent, the first such statement in the online case.

######  Corollary 19.

Let $\mathcal{F}$ be a $(c,p)$-bounded class of functions. If $\ell$ is an
$L$-Lipschitz function, we have

$\mathcal{R}_{n}\left(\ell\circ\mathcal{F}\right)~{}\lesssim~{}L\mathcal{R}_{n}(\mathcal{F})$
(36)

where, again, the constant depends on $\mathcal{F}$ only through $c$ and $p$.

Importantly, the statement of Corollary 19 is one about _worst-case_
Rademacher complexity as opposed to _tree-dependent_ Rademacher complexity. A
similar statement with a factor polynomial in $\log n$ was proved as (Rakhlin
et al. ,, 2015, Lemma 7). Whether an analogous result holds in the tree-
dependent case remains a challenging open question.

##  5 Sample Complexity of Online Learning

We finish this paper with a discussion of online learning, showing that our
techniques lead to sharp estimates on minimax regret.

The online supervised learning problem is defined as follows. We fix a class
of functions $\mathcal{F}\subseteq[-1,1]^{\mathcal{X}}$, known to the learner.
The online prediction problem proceeds over $n$ rounds. On round $t$, the
learner observes $x_{t}\in\mathcal{X}$, makes a prediction
$\widehat{y}_{t}\in\mathbb{R}$, and observes the outcome
$y_{t}\in\mathcal{Y}\subseteq\mathbb{R}$. Predictions may be randomized, in
which case the learner selects a distribution $q_{t}$ on round $t$ and draws
$\widehat{y}_{t}\sim q_{t}$. Regret is defined as

$\displaystyle\mathsf{Reg}_{n}(\mathcal{F})=\mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n}\ell(\widehat{y}_{t},y_{t})-\inf_{f\in\mathcal{F}}\frac{1}{n}\sum_{t=1}^{n}\ell(f(x_{t}),y_{t})\right].$
(37)

In turn, the minimax regret is defined as

$\displaystyle
V_{n}(\mathcal{F})=\min_{\tau}\max_{\pi}~{}\mathsf{Reg}_{n}(\mathcal{F})$ (38)

where minimum is taken over all randomized strategies of the learner, and
maximum is over all strategies of Nature for selecting the sequence
(potentially adaptively and adversarially). While this minimax object appears
to be complicated, by writing down a repeated sequence of minima and maxima
per time step, it is possible to upper bound the minimax regret by a supremum
of a collection of martingales indexed by $\mathcal{F}$ (Abernethy et al. ,,
2009; Rakhlin et al. ,, 2010). In particular, it is shown in (Rakhlin et al.
,, 2010) that for binary classification with $\mathcal{Y}=\\{0,1\\}$,
$\mathcal{F}\subseteq\mathcal{Y}^{\mathcal{X}}$, and
$\ell(a,b)=\mathbb{I}\\{a\neq b\\}$,

$\displaystyle\mathcal{R}_{n}(\mathcal{F})\leq V_{n}(\mathcal{F})\leq
2\mathcal{R}(\mathcal{F})$ (39)

where
$\mathcal{R}_{n}(\mathcal{F})=\sup_{{\boldsymbol{x}}}\mathcal{R}_{n}(\mathcal{F},{\boldsymbol{x}})$.
The tight characterization (39) also holds for prediction with absolute value
loss ($\ell(a,b)=|a-b|$, $\mathcal{Y}=[-1,1],$ and
$\mathcal{F}\subseteq\mathcal{Y}^{\mathcal{X}}$), as well as for prediction
with linear loss ($\ell(a,b)=-ab$,
$\mathcal{Y}=[-1,1],\mathcal{F}\subseteq\mathcal{Y}^{\mathcal{X}}$) (Rakhlin
et al. ,, 2010).

For the online learning problems mentioned above, we conclude that

$\displaystyle V_{n}(\mathcal{F})~{}\lesssim~{}\inf_{\alpha\geq
0}\left\\{\alpha+\frac{1}{\sqrt{n}}\int_{\alpha}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta\right\\},$
(40)

improving on the corresponding estimates in (Rakhlin et al. ,, 2010). In
particular, from Corollary 18, for classes satisfying Definition 17, the
minimax regret

$\displaystyle
V_{n}(\mathcal{F})~{}\asymp~{}\frac{1}{\sqrt{n}}\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta~{}\asymp~{}\sqrt{\frac{c}{n}}.$
(41)

In particular, for binary classification, this recovers the sharp result of
(Alon et al. ,, 2021), as $\mathsf{fat}_{\delta}(\mathcal{F})$ reduces to the
Littlestone dimension in this case. More generally, (40) provides a succinct
and sharp characterization of optimal regret in terms of combinatorial
parameters of the class. Using the techniques developed in this paper, we can
sharpen and remove extraneous logarithmic factors in a number of bounds in
(Rakhlin et al. ,, 2010). We mention that for online regression with square
loss, optimal regret is characterized in terms of a localized notion of
sequential Rademacher complexity (offset complexity), and the study of its
behavior in terms of the notions introduced in this paper is left for future
work.

## Acknowledgements

AB acknowledges support from the National Science Foundation Graduate Research
Fellowship under Grant No. 1122374. AR acknowledges support from the ONR
through award #N00014-20-1-2336.

## References

  * Abernethy et al. , (2009) Abernethy, Jacob, Agarwal, Alekh, Bartlett, Peter L, & Rakhlin, Alexander. 2009\.  A stochastic view of optimal regret through minimax duality.  arXiv preprint arXiv:0903.5328.
  * Alon et al. , (2019) Alon, Noga, Livni, Roi, Malliaris, Maryanthe, & Moran, Shay. 2019.  Private PAC learning implies finite littlestone dimension.  Pages 852–860 of: 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019.  Association for Computing Machinery.
  * Alon et al. , (2021) Alon, Noga, Ben-Eliezer, Omri, Dagan, Yuval, Moran, Shay, Naor, Moni, & Yogev, Eylon. 2021.  Adversarial Laws of Large Numbers and Optimal Regret in Online Classification.
  * Bartlett et al. , (2008) Bartlett, Peter, Dani, Varsha, Hayes, Thomas, Kakade, Sham, Rakhlin, Alexander, & Tewari, Ambuj. 2008.  High-probability regret bounds for bandit online linear optimization.  Pages 335–342 of: Proceedings of the 21st Annual Conference on Learning Theory-COLT 2008.  Omnipress.
  * Bartlett & Mendelson, (2002) Bartlett, Peter L, & Mendelson, Shahar. 2002.  Rademacher and Gaussian complexities: Risk bounds and structural results.  Journal of Machine Learning Research, 3(Nov), 463–482.
  * Bartlett et al. , (1996) Bartlett, Peter L, Long, Philip M, & Williamson, Robert C. 1996.  Fat-shattering and the learnability of real-valued functions.  journal of computer and system sciences, 52(3), 434–452.
  * Ben-David et al. , (2009) Ben-David, Shai, Pál, Dávid, & Shalev-Shwartz, Shai. 2009.  Agnostic Online Learning.  Page 1 of: COLT, vol. 3.
  * Bercu & Touati, (2008) Bercu, Bernard, & Touati, Abderrahmen. 2008.  Exponential inequalities for self-normalized martingales with applications.  The Annals of Applied Probability, 18(5), 1848–1869.
  * Bun et al. , (2020) Bun, Mark, Livni, Roi, & Moran, Shay. 2020.  An Equivalence Between Private Classification and Online Prediction.  In: 61st Annual IEEE Symposium on Foundations of Computer Science.
  * Cesa-Bianchi & Lugosi, (2006) Cesa-Bianchi, Nicolo, & Lugosi, Gábor. 2006.  Prediction, learning, and games.  Cambridge university press.
  * de la Peña, (1999) de la Peña, Victor H. 1999.  A general class of exponential inequalities for martingales and ratios.  The Annals of Probability, 27(1), 537–564.
  * Dudley, (1973) Dudley, R. M. 1973.  Sample Functions of the Gaussian Process.  Ann. Probab., 1(1), 66–103.
  * Fernique, (1975) Fernique, Xavier. 1975.  Regularité des trajectoires des fonctions aléatoires gaussiennes.  Pages 1–96 of: Ecole d’Eté de Probabilités de Saint-Flour IV—1974.  Springer.
  * Foster & Rakhlin, (2020) Foster, Dylan, & Rakhlin, Alexander. 2020.  Beyond UCB: Optimal and efficient contextual bandits with regression oracles.  Pages 3199–3210 of: International Conference on Machine Learning.  PMLR.
  * Foster et al. , (2020) Foster, Dylan, Sarkar, Tuhin, & Rakhlin, Alexander. 2020.  Learning nonlinear dynamical systems from a single trajectory.  Pages 851–861 of: Learning for Dynamics and Control.  PMLR.
  * Ghazi et al. , (2020) Ghazi, Badih, Golowich, Noah, Kumar, Ravi, & Manurangsi, Pasin. 2020.  Sample-efficient proper PAC learning with approximate differential privacy.  arXiv preprint arXiv:2012.03893.
  * Giné & Zinn, (1984) Giné, Evarist, & Zinn, Joel. 1984.  Some limit theorems for empirical processes.  The Annals of Probability, 929–989.
  * Hall et al. , (2016) Hall, Eric C, Raskutti, Garvesh, & Willett, Rebecca. 2016.  Inference of high-dimensional autoregressive generalized linear models.  arXiv preprint arXiv:1605.02693.
  * Jung et al. , (2020) Jung, Young, Kim, Baekjin, & Tewari, Ambuj. 2020.  On the Equivalence between Online and Private Learnability beyond Binary Classification.  Advances in Neural Information Processing Systems, 33.
  * Kearns & Schapire, (1994) Kearns, Michael J, & Schapire, Robert E. 1994.  Efficient distribution-free learning of probabilistic concepts.  Journal of Computer and System Sciences, 48(3), 464–497.
  * Littlestone, (1988) Littlestone, Nick. 1988.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  Machine learning, 2(4), 285–318.
  * Mendelson & Vershynin, (2003) Mendelson, Shahar, & Vershynin, Roman. 2003.  Entropy and the combinatorial dimension.  Inventiones mathematicae, 152(1), 37–55.
  * Rakhlin & Sridharan, (2015) Rakhlin, Alexander, & Sridharan, Karthik. 2015.  On Martingale Extensions of Vapnik–Chervonenkis Theory with Applications to Online Learning.  Pages 197–215 of: Measures of Complexity.  Springer.
  * Rakhlin et al. , (2010) Rakhlin, Alexander, Sridharan, Karthik, & Tewari, Ambuj. 2010.  Online Learning: Random Averages, Combinatorial Parameters, and Learnability.  Advances in Neural Information Processing Systems, 23, 1984–1992.
  * Rakhlin et al. , (2015) Rakhlin, Alexander, Sridharan, Karthik, & Tewari, Ambuj. 2015.  Sequential complexities and uniform martingale laws of large numbers.  Probability Theory and Related Fields, 161(1-2), 111–153.
  * Rudelson & Vershynin, (2006) Rudelson, Mark, & Vershynin, Roman. 2006.  Combinatorics of random processes and sections of convex bodies.  Annals of Mathematics, 603–648.
  * Talagrand, (1996) Talagrand, Michel. 1996.  Majorizing measures: the generic chaining.  The Annals of Probability, 24(3), 1049–1103.
  * Talagrand, (2014) Talagrand, Michel. 2014.  Upper and lower bounds for stochastic processes: modern methods and classical problems.  Vol. 60.  Springer Science & Business Media.
  * van Handel, (2014) van Handel, Ramon. 2014.  Probability in high dimension.  Tech. rept. PRINCETON UNIV NJ.
  * Vapnik & Chervonenkis, (1971) Vapnik, VN, & Chervonenkis, A Ya. 1971.  On uniform convergence of the frequencies of events to their probabilities.  Teoriya Veroyatnostei i ee Primeneniya, 16(2), 264–279.
  * Vapnik & Chervonenkis, (1981) Vapnik, VN, & Chervonenkis, A Ya. 1981.  The necessary and sufficient conditions for the uniform convergence of averages to their expected values.  Teoriya Veroyatnostei i Ee Primeneniya, 26(3), 543–564.

##  Appendix A Proof of Theorem 3

We use the technique of chaining. In order to apply it, we need an adaptive
tail bound for the tree process. We have

######  Lemma 20.

Let ${\boldsymbol{v}}$ be a labelled binary tree and let
$\varepsilon_{1},\dots,\varepsilon_{n}$ be independent Rademacher random
variables. Then for any $y>0$, with probability at least $1-\rho$, we have

$\sum_{t=1}^{n}{\boldsymbol{v}}_{t}(\varepsilon)^{2}\leq y$ (42)

implies that

$\left|\sum_{t=1}^{n}\varepsilon_{t}{\boldsymbol{v}}_{t}(\varepsilon)\right|\leq
2\sqrt{2y\log\frac{1}{\rho}}$ (43)

###### Proof.

Let

$M_{s}=\sum_{t\leq s}\varepsilon_{t}{\boldsymbol{v}}_{t}(\varepsilon)$ (44)

Note that $M_{s}$ is a martingale with conditionally symmetric increments
because the $\varepsilon_{t}$ are independent and the ${\boldsymbol{v}}_{t}$
are adapted. Note that the quadratic variation is given by
$[M_{s}]=\sum_{t=1}^{n}{\boldsymbol{v}}_{t}(\varepsilon)^{2}$. Thus by de la
Pena’s inequality (see de la Peña, (1999); Bercu & Touati, (2008)), we have
for any $x,y>0$,

$\mathbb{P}\left(\left|M_{T}\right|\geq x,\,\,[M_{T}]\leq y\right)\leq
2e^{-\frac{x^{2}}{2y}}$ (45)

Setting $x=2\sqrt{2y\log\frac{1}{\rho}}$ concludes the proof. ∎

Using Lemma 20, we are able to prove Lemma 4.

###### Proof of Lemma 4.

Let $y_{j}=2^{-j}n$ and let $\rho_{j}=\rho j^{-2}$. Then for any fixed $j$,
Lemma 20 tells us that

$\displaystyle\mathbb{P}\left(\left|\mathbb{T}_{\boldsymbol{v}}\right|>C\sqrt{y_{j}\log\frac{j}{\rho}}\text{
and }\left|\left|{\boldsymbol{v}}\right|\right|^{2}\leq
y_{j}\right)\leq\frac{6}{\pi^{2}}\rho_{j}$ (46)

for some $C$. Summing $\frac{6}{\pi^{2}}\rho_{j}$ gives $\rho$ and so a union
bound tells us that with probability at least $1-\rho$, for all $j$,

$\displaystyle\textbf{If}\quad\left|\left|{\boldsymbol{v}}\right|\right|\leq\sqrt{n2^{-j}}$
$\displaystyle\textbf{Then}\quad\left|\mathbb{T}_{\boldsymbol{v}}\right|\leq
C\sqrt{n2^{-j}\log\frac{j}{\rho}}$ (47)

On the event that $\left|\left|{\boldsymbol{v}}\right|\right|=0$ the result is
trivial. Thus, suppose otherwise and take $j=\lceil
e\log\frac{n}{\left|\left|{\boldsymbol{v}}\right|\right|^{2}}\rceil$; the
above holds. Plugging in, we see that the “if” statement is valid for this $j$
and thus we have

$\displaystyle\left|\mathbb{T}_{\boldsymbol{v}}\right|\leq
C\sqrt{n2^{-j}\log\frac{j}{\rho}}\leq
C\sqrt{\left|\left|{\boldsymbol{v}}\right|\right|^{2}\log\frac{\log\frac{en}{\left|\left|{\boldsymbol{v}}\right|\right|^{2}}}{\rho}}$
(48)

with probability at least $1-\rho$. ∎

We will also need a lemma to relate probability over the majorizing measure to
probability over the $\varepsilon$. We have:

######  Lemma 21.

Let $\mu$ a measure over binary trees ${\boldsymbol{v}}$ and consider
indicator variables $U({\boldsymbol{v}},\varepsilon)$ and let
$\alpha,\rho\in(0,1)$. Suppose that for each
${\boldsymbol{v}}\in\operatorname{supp}\mu$,
$\mathbb{E}_{\varepsilon}(U({\boldsymbol{v}},\varepsilon))\leq\alpha\rho$.
Then with probability at least $1-\rho$ on the $\varepsilon$,

$\mathbb{E}_{\mu}\left(U({\boldsymbol{v}},\varepsilon)\right)\leq\alpha$ (49)

###### Proof.

This follows immediately from Fubini’s theorem and Markov’s inequality. ∎

We are now ready to prove the main chaining bound with the fractional covering
number. For ${\boldsymbol{v}},{\boldsymbol{v}}^{\prime}\in\mathcal{V}$ binary
trees, we fix

$\displaystyle\mathbb{T}_{{\boldsymbol{v}},{\boldsymbol{v}}^{\prime}}(\varepsilon)=\sum_{t=1}^{n}\varepsilon_{t}({\boldsymbol{v}}_{t}(\varepsilon)-{\boldsymbol{v}}_{t}^{\prime}(\varepsilon))$
(50)

and we recall that the norm is

$\displaystyle\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|=\sum_{t=1}^{n}({\boldsymbol{v}}_{t}(\varepsilon)-{\boldsymbol{v}}_{t}^{\prime}(\varepsilon))^{2}$
(51)

With this notation fixed, we can prove the theorem.

We prove the following lemma:

######  Lemma 22.

Let $\mu$ be a probability distribution over $[0,1]$ valued trees of depth $n$
and define $\nu=\mu\otimes\mu$. With probability $1-\rho$, the following
holds: uniformly, for any $\gamma\geq 2$,

$\displaystyle\mu\left(\left\\{{\boldsymbol{v}}\colon\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>C\sqrt{n\log\frac{\gamma}{\rho}}\right\\}\right)\leq\frac{1}{\gamma}$
(52)
$\displaystyle\nu\left(\left\\{({\boldsymbol{v}},{\boldsymbol{v}}^{\prime})\colon\left|\mathbb{T}_{{\boldsymbol{v}},{\boldsymbol{v}}^{\prime}}(\varepsilon)\right|>C\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|\sqrt{\log\frac{\gamma}{\rho}+\log\log\frac{3\sqrt{n}}{\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|}}\right\\}\right)\leq\frac{1}{\gamma}$
(53)

###### Proof.

We first note that it suffices to prove the result uniformly on
$\gamma_{j}=2^{j}$. For any $\gamma$, let $\gamma_{j}$ maximal power of $2$
that is at most $\gamma$. Then the sets in the statement of the lemma for
$\gamma$ are contained in the corresponding sets for $\gamma_{j}$. Moreover,
$\gamma_{j}$ differs from $\gamma$ by at most a factor of $2$, that can be
eaten into the constants $C$ in the statement. More formally, we have

$\displaystyle\mu\left(\left\\{{\boldsymbol{v}}\colon\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>2C\sqrt{n\log\frac{\gamma}{\rho}}\right\\}\right)$
$\displaystyle\leq\mu\left(\left\\{{\boldsymbol{v}}\colon\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>C\sqrt{n\log\frac{\gamma}{2\rho}}\right\\}\right)$
(54)
$\displaystyle\leq\mu\left(\left\\{{\boldsymbol{v}}\colon\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>C\sqrt{n\log\frac{\gamma_{j}}{2\rho}}\right\\}\right)$
(55) $\displaystyle\leq\frac{2}{\gamma_{j}}\leq\frac{1}{\gamma}$ (56)

and similarly for the other event; thus, it suffices to prove the result only
for $\gamma$ powers of $2$.

Now, setting $y=\sqrt{n}$ and applying Lemma 20, we get

$\displaystyle\mathbb{P}\left(\left\\{\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>C\sqrt{n\log\frac{\gamma_{j}^{2}}{\rho}}\right\\}\right)$
$\displaystyle=\mathbb{P}\left(\left\\{\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>C\sqrt{n\log\frac{\gamma_{j}^{2}}{\rho}}\text{
and
}\left|\left|{\boldsymbol{v}}(\varepsilon)\right|\right|\leq\sqrt{n}\right\\}\right)$
(57) $\displaystyle\leq\frac{\rho}{6\gamma_{j}^{2}}$ (58)

for $C$ large enough, where the equality follows from the fact that
$\left|{\boldsymbol{v}}_{t}(\varepsilon)\right|\leq 1$ and so
$\left|\left|{\boldsymbol{v}}(\varepsilon)\right|\right|\leq\sqrt{n}$ almost
surely. Applying Lemma 21 tells us that for all $j$, with probability at least
$1-\frac{\rho}{6\gamma_{j}}$, we have

$\mu\left(\left\\{{\boldsymbol{v}}\colon\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>C\sqrt{n\log\frac{\gamma_{j}^{2}}{\rho}}\right\\}\right)\leq\frac{1}{\gamma_{j}}$
(59)

Taking a union bound and noting that $\frac{1}{\gamma_{j}}=2^{-j}$ is
summable, then pulling the square out of the log factor tells us that with
probability at least $1-\frac{\rho}{6}$, we have, uniformly in $j$,

$\mu\left(\left\\{{\boldsymbol{v}}\colon\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>C\sqrt{n\log\frac{\gamma_{j}}{\rho}}\right\\}\right)\leq\frac{1}{\gamma_{j}}$
(60)

Now we look at the second event. The identical argument serves to allow us to
only consider $\gamma_{j}$. We now apply Lemma 4 to Lemma 21 instead of Lemma
20. In particular, note that for any $\gamma_{j}$, and any
${\boldsymbol{v}},{\boldsymbol{v}}^{\prime}$, we have

$\displaystyle\mathbb{P}\left(\left|\mathbb{T}_{{\boldsymbol{v}},{\boldsymbol{v}}^{\prime}}(\varepsilon)\right|>C\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|\sqrt{\log\frac{6\gamma_{j}^{2}}{\rho}+\log\log\frac{6\sqrt{n}}{\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|}}\right)\leq\frac{\rho}{6\gamma_{j}^{2}}$
(61)

by Lemma 4. Thus, applying Lemma 21 with the measure $\nu$, we have that with
probability at least $1-\frac{\rho}{\gamma_{j}}$,

$\displaystyle\nu\left(\left\\{({\boldsymbol{v}},{\boldsymbol{v}}^{\prime})\colon\left|\mathbb{T}_{{\boldsymbol{v}},{\boldsymbol{v}}^{\prime}}(\varepsilon)\right|>C\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|\sqrt{\log\frac{\gamma_{j}^{2}}{\rho}+\log\log\frac{3\sqrt{n}}{\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|}}\right\\}\right)\leq\frac{1}{\gamma_{j}}$
(62)

Applying a union bound and taking out the square from the logarithm and
putting it into the constant $C$ concludes the proof. ∎

For the remainder, assume that the event of Lemma 22 holds and we will show
how to bound the supremum over $\mathbb{T}_{f({\boldsymbol{z}})}$. Define
$\delta_{j}=2^{-j}$ and for any $f,\varepsilon$, define
$\gamma_{j}(f,\varepsilon)=1/\mu(B_{\delta_{j}}(f,\varepsilon))$. Let $N$ be
the maximal integer such that $\delta^{N}\geq 2\alpha$.

Notice that it suffices to prove that (under the event of Lemma 22), for any
$f\in\mathcal{F}$,

$\displaystyle\mathbb{T}_{f}(\varepsilon)$ $\displaystyle\leq
C\left(\sqrt{n\log\frac{1}{\rho}}+n\delta_{N}+\sqrt{n}\sum_{j=0}^{N}\delta_{j}\sqrt{\log\gamma_{j}(f,\varepsilon)}\right)$
(63) $\displaystyle\leq
C\left(\sqrt{n\log\frac{1}{\rho}}+n\alpha+\sqrt{n}\sum_{j=0}^{N}2^{-j}\sqrt{\log\frac{1}{\mu(B_{2^{-j}}(f,\varepsilon))}}\right).$
(64)

Define

$\displaystyle
r_{j}(f,\varepsilon)=C\delta_{j}\sqrt{n}\sqrt{\log\frac{\gamma_{j+1}(f,\varepsilon)}{\rho}+\log\log\frac{3}{\delta_{j}}}$
(65)

for a sufficiently large $C>0$ and $j\geq 0$ integer. We write $r_{j}$ and
$\gamma_{j}$ when $f,\varepsilon$ are obvious from context. We have that the
following holds for any $f,\varepsilon$ and $j\geq 1$ (we refer to these
inequalities as $(\dagger)$):

$\displaystyle\mu\left(\left\\{{\boldsymbol{v}}\colon\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>r_{0}(f,\varepsilon)\right\\}\right)\leq\frac{1}{4\gamma_{0}(f,\varepsilon)}$
(66)
$\displaystyle\nu\left(\left\\{({\boldsymbol{v}},{\boldsymbol{v}}^{\prime})\colon\left|\mathbb{T}_{{\boldsymbol{v}},{\boldsymbol{v}}^{\prime}}(\varepsilon)\right|>r_{j}(f,\varepsilon)\text{
and
}\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}(\varepsilon^{\prime})\right|\right|\leq
2\delta_{j}\sqrt{n}\right\\}\right)$ (67)
$\displaystyle\leq\frac{1}{9\gamma_{j}(f,\varepsilon)\gamma_{j+1}(f,\varepsilon)}.$
(68)

Indeed, the first inequality is obtained from Lemma 22 by substituting
$\gamma=4\gamma_{0}(f,\varepsilon)$ and the second inequality is obtained by
taking $\gamma=9\gamma_{j}(f,\varepsilon)\gamma_{j+1}(f,\varepsilon)\leq
9\gamma_{j+1}(f,\varepsilon)^{2}$.

Our goal is to construct a chain of elements
${\boldsymbol{v}}_{f,0},\dots,{\boldsymbol{v}}_{f,N}$ that provide finer and
finer approximations for $f({\boldsymbol{z}})$ on the path $\varepsilon$, and
obtain the bound

$\mathbb{T}_{f({\boldsymbol{z}})}\leq\mathbb{T}_{{\boldsymbol{v}}_{f,0}}+\sum_{j=0}^{N-1}\mathbb{T}_{{\boldsymbol{v}}_{f,j},{\boldsymbol{v}}_{f,j+1}}+\mathbb{T}_{{\boldsymbol{v}}_{f,N},f({\boldsymbol{z}})}.$

The approximations will be chosen from the sets
$A^{\prime}_{j}(f,\varepsilon)$ defined below:

$\displaystyle A_{j}(f,\varepsilon)$
$\displaystyle=\left\\{{\boldsymbol{v}}|\left|\left|{\boldsymbol{v}}(\varepsilon)-f({\boldsymbol{z}}(\varepsilon))\right|\right|\leq\sqrt{n}\delta_{j}\right\\}$
(69) $\displaystyle A_{j}^{\prime}(f,\varepsilon)$
$\displaystyle=\left\\{{\boldsymbol{v}}\in
A_{j}(f,\varepsilon)\colon\mu\left(\left\\{{\boldsymbol{v}}^{\prime}|\left|\mathbb{T}_{{\boldsymbol{v}},{\boldsymbol{v}}^{\prime}}(\varepsilon)\right|>r_{j}(f,\varepsilon)\text{
and
}\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|\leq
2\delta_{j}\sqrt{n}\right\\}\right)\leq\frac{1}{3\gamma_{j+1}}\right\\}$ (70)

As a first step, we would like to lower bound
$\mu(A_{j}^{\prime}(f,\varepsilon))$ assuming we have $\varepsilon$ such that
($\dagger$) holds. By construction,
$\mu(A_{j}(f,\varepsilon))\geq\frac{1}{\gamma_{j}(f,\varepsilon)}$. For any
${\boldsymbol{v}}$, let

$B({\boldsymbol{v}})=\left\\{{\boldsymbol{v}}^{\prime}|\left|\mathbb{T}_{{\boldsymbol{v}},{\boldsymbol{v}}^{\prime}}(\varepsilon)\right|>r_{j}(f,\varepsilon)\text{
and
}\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|\leq
2\delta_{j}\sqrt{n}\right\\}$ (71)

and let

$B=\bigcup_{\boldsymbol{v}}\bigcup_{{\boldsymbol{v}}^{\prime}\in
B({\boldsymbol{v}})}\left\\{({\boldsymbol{v}},{\boldsymbol{v}}^{\prime})\right\\}$
(72)

Let

$\widetilde{B}=\left\\{{\boldsymbol{v}}|\mu(B({\boldsymbol{v}}))>\frac{1}{3\gamma_{j+1}}\right\\}$
(73)

From ($\dagger$), we know that $\nu(B)\leq\frac{1}{9\gamma_{j}\gamma_{j+1}}$.
By construction of $\nu$, we have

$\displaystyle\nu(B)\geq\mu\left(B({\boldsymbol{v}})|{\boldsymbol{v}}\in\widetilde{B}\right)\mu\left(\widetilde{B}\right)$
(74)

By construction, if ${\boldsymbol{v}}\in\widetilde{B}$, then

$\mu\left(B({\boldsymbol{v}})\right)\geq\frac{1}{3\gamma_{j+1}}$ (75)

Thus we have

$\displaystyle\mu\left(\widetilde{B}\right)\leq\frac{\nu(B)}{\mu\left(B({\boldsymbol{v}})|{\boldsymbol{v}}\in\widetilde{B}\right)}\leq\frac{\frac{1}{9\gamma_{j}\gamma_{j+1}}}{\frac{1}{3\gamma_{j+1}}}=\frac{1}{3\gamma_{j}}$
(76)

Thus we see that

$\mu(A_{j}^{\prime}(f,\varepsilon))\geq\mu(A_{j}(f,\varepsilon))-\mu(\widetilde{B})\geq\frac{1}{\gamma_{j}}-\frac{1}{3\gamma_{j}}=\frac{2}{3\gamma_{j}}\enspace.$
(77)

As a final remark before we construct the chain, note that if
${\boldsymbol{v}}\in A_{j}(f,\varepsilon)$ and ${\boldsymbol{v}}^{\prime}\in
A_{j+1}(f,\varepsilon)$, then by the triangle inequality,

$\left|\left|{\boldsymbol{v}}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|\leq\left|\left|{\boldsymbol{v}}(\varepsilon)-f({\boldsymbol{z}}(\varepsilon))\right|\right|+\left|\left|{\boldsymbol{v}}^{\prime}(\varepsilon)-f({\boldsymbol{z}}(\varepsilon))\right|\right|\leq\delta_{j}\sqrt{n}+\delta_{j+1}\sqrt{n}\leq
2\delta_{j}\sqrt{n}$ (78)

We are now ready to construct the chain. Fix $\varepsilon$ such that
($\dagger$) holds. For notational simplicity, we suppress the dependence of
${\boldsymbol{v}}_{f,j,\varepsilon}$ on $\varepsilon$ and simply write
${\boldsymbol{v}}_{f,j}$; this causes no confusion as we have fixed
$\varepsilon$. For any $f$, we have

$\displaystyle\mu\left(A_{j}^{\prime}(f,\varepsilon)\cap\left\\{{\boldsymbol{v}}|\left|\mathbb{T}_{\boldsymbol{v}}(\varepsilon)\right|>r_{j}(f,\varepsilon)\right\\}^{c}\right)\geq\frac{2}{3\gamma_{j}}-\frac{1}{3\gamma_{j}}=\frac{1}{3\gamma_{j}}>0$
(79)

Thus, letting $j=0$, we see that there exists a ${\boldsymbol{v}}_{f,0}\in
A_{0}^{\prime}(f,\varepsilon)$ such that

$\left|\mathbb{T}_{{\boldsymbol{v}}_{f,0}}(\varepsilon)\right|\leq
r_{0}(f,\varepsilon).$ (80)

Now suppose that we have chosen ${\boldsymbol{v}}_{f,j}\in
A_{j}^{\prime}(f,\varepsilon)$. We wish to select an element
${\boldsymbol{v}}_{f,j+1}\in A_{j+1}^{\prime}(f,\varepsilon)$ such that
$\left|\mathbb{T}_{{\boldsymbol{v}}_{f,j},{\boldsymbol{v}}_{f,j+1}}(\varepsilon)\right|$
is small. To see that this is possible, we remark that, as
${\boldsymbol{v}}_{f,j}\in A_{j}^{\prime}(f,\varepsilon)$, we have by
definition

$\displaystyle\mu\left(\left\\{{\boldsymbol{v}}^{\prime}|\left|\mathbb{T}_{{\boldsymbol{v}}_{f,j},{\boldsymbol{v}}^{\prime}}(\varepsilon)\right|>r_{j}(f,\varepsilon)\text{
and
}\left|\left|{\boldsymbol{v}}_{f,j}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|\leq
2\delta_{j}\sqrt{n}\right\\}\right)\leq\frac{1}{3\gamma_{j+1}}$ (81)

But we have already seen that

$\displaystyle\mu(A_{j+1}^{\prime}(f,\varepsilon))\geq\frac{2}{3\gamma_{j+1}}$
(82)

and as noted, for any ${\boldsymbol{v}}^{\prime}\in
A_{j+1}^{\prime}(f,\varepsilon)$,
$\left|\left|{\boldsymbol{v}}_{f,j}(\varepsilon)-{\boldsymbol{v}}^{\prime}(\varepsilon)\right|\right|\leq
2\delta_{j}\sqrt{n}$. Thus $\mu$ takes measure at least
$\frac{1}{3\gamma_{j+1}}$ on the set of such desirable next links in the chain
and so such a ${\boldsymbol{v}}_{f,j+1}$ exists. Thus for any $f$, on this
$\varepsilon$, we have a chain ${\boldsymbol{v}}_{f,j}$ for $j\geq 0$ such
that ${\boldsymbol{v}}_{f,j}\in A_{j}^{\prime}(f,\varepsilon)$. Note that, by
(78) and the way we have constructed the chain, we have that for all $f$,

$\left|\mathbb{T}_{{\boldsymbol{v}}_{f,j},{\boldsymbol{v}}_{f,j+1}}(\varepsilon)\right|\leq
r_{j}(f,\varepsilon).$ (83)

We also have for any $f$ that

$\left|\mathbb{T}_{{\boldsymbol{v}}_{f,0}}\right|\leq r_{0}(f,\varepsilon).$
(84)

Thus we see that on this $\varepsilon$, for every $f$,

$\displaystyle\mathbb{T}_{f}(\varepsilon)$
$\displaystyle=\mathbb{T}_{{\boldsymbol{v}}_{f,0,\varepsilon}}(\varepsilon)+\sum_{N\geq
j\geq
0}\mathbb{T}_{{\boldsymbol{v}}_{f,j,\varepsilon},{\boldsymbol{v}}_{f,j+1,\varepsilon}}(\varepsilon)+\mathbb{T}_{f({\boldsymbol{z}}),{\boldsymbol{v}}_{f,N,\varepsilon}}(\varepsilon)$
(85) $\displaystyle\leq
r_{0}(f,\varepsilon)+\sum_{j=0}^{N-1}r_{j}(f,\varepsilon)+Cn\delta_{n}(f,\varepsilon)$
(86) $\displaystyle\leq
C\sqrt{n\log\frac{1}{\rho}}+\sum_{j=0}^{N-1}C\sqrt{n}\left(\sqrt{\log\gamma_{j}(f,\varepsilon)}+\sqrt{\log\log\frac{3}{\delta_{j}}}\right)\delta_{j}+\delta_{N}(f,\varepsilon)n$
(87) $\displaystyle\leq
C\sqrt{n\log\frac{1}{\rho}}+\sum_{j=0}^{N-1}C\sqrt{n}\sqrt{\log\gamma_{j}(f,\varepsilon)}\delta_{j}+\delta_{N}(f,\varepsilon)n$
(88)

where the inequality
$\mathbb{T}_{f({\boldsymbol{z}}),{\boldsymbol{v}}_{f,N,\varepsilon}}(\varepsilon)$
follows from Cauchy-schwarz and the fact that ${\boldsymbol{v}}_{f,N}\in
A_{N}(f,\varepsilon)$. As ($\dagger$) occurs with probability at least
$1-\rho$, we have with the same probability that the above is bounded. This
concludes the proof.

##  Appendix B Proof of Theorem 13

In this appendix, we prove the auxiliary lemmata required to complete the
proof of Theorem 13. We begin with a result from Rakhlin et al. , (2015):

######  Lemma 23 (Rakhlin et al. , (2015)).

Let ${\boldsymbol{z}}$ be a $\mathcal{Z}$-valued binary tree, $\mathcal{F}$ a
class of functions $\mathcal{Z}\to\\{0,1,\dots,m\\}$, ${\boldsymbol{z}}_{0}$
the root of the tree, and
$\mathcal{F}_{j}=\\{f\in\mathcal{F}|f({\boldsymbol{z}}_{0})=j\\}$. Let $r\geq
1$ be an integer. If $j,j^{\prime}\in\\{0,\dots,m\\}$ such that
$\mathsf{fat}_{r}(\mathcal{F}_{j})=\mathsf{fat}_{r}(\mathcal{F}_{j^{\prime}})=\mathsf{fat}_{r}(\mathcal{F})$,
then $|j-j^{\prime}|<r$. In particular, there can be at most $r$ values of $j$
such that $\mathsf{fat}_{r}(\mathcal{F}_{j})=\mathsf{fat}_{r}(\mathcal{F})$.

###### Proof.

Suppose that $j,j^{\prime}\in\\{0,\dots,m\\}$ such that $j\geq j^{\prime}+r$.
Let ${\boldsymbol{z}}^{(-1)}$ and ${\boldsymbol{z}}^{(1)}$ denote trees of
depth $\mathsf{fat}_{r}(\mathcal{F})$ that shatter at scale $r$ the classes
$\mathcal{F}_{j}$ and $\mathcal{F}_{j^{\prime}}$. Then, we can construct a
tree of depth $\mathsf{fat}_{r}(\mathcal{F})+1$ that $r$-shatters
$\mathcal{F}$ by taking $z_{0}$ as a root and taking $z^{(\pm 1)}$ as subtrees
of the root. This contradicts the fact that $\mathsf{fat}_{r}(\mathcal{F})$ is
the maximal depth of a tree that shatters $\mathcal{F}$ at scale $r$. The
result follows. ∎

We now provide the detailes for the proof of Proposition 14, sketched in the
text.

###### Proof of Proposition 14.

Given a tree ${\boldsymbol{z}}$ and $\mathcal{F}$, we construct the fractional
cover $\mu_{{\boldsymbol{z}},\mathcal{F}}$ recursively. If ${\boldsymbol{z}}$
is an empty tree then define $\mu_{{\boldsymbol{z}},\mathcal{F}}$ to have a
unit mass on the empty tree. Otherwise, define by ${\boldsymbol{z}}_{0}$,
${\boldsymbol{z}}^{(-1)}$ and ${\boldsymbol{z}}^{(1)}$ its root and left and
right subtrees, respectively (if the tree has depth zero then
${\boldsymbol{z}}^{(\pm 1)}$ are emty trees). Further, define
$\mathcal{F}_{j}=\left\\{f\in\mathcal{F}:f({\boldsymbol{z}}_{0})=j\right\\}$
for $0\leq j\leq m$. We form $\mu$ as a mixture of measures
$\mu_{z,\mathcal{F}_{j},j}$ and $\mu_{{\boldsymbol{z}},\mathcal{F},j}$, where
$\mu_{{\boldsymbol{z}},\mathcal{G},j}$ is defined as the measure on
$\mathcal{Y}$-valued trees $v$ such that the root is labeled by $i$ almost
surely and the left and right subtrees are sampled independently from
$\mu_{{\boldsymbol{z}}^{(-1)},\mathcal{G}}$ and
$\mu_{{\boldsymbol{z}}^{(1)},\mathcal{G}}$.

To define the mixture coefficients, we use Lemma 23 which tells us that if
$j<j^{\prime}$ are such that
$\mathsf{fat}_{2}(\mathcal{F}_{j})=\mathsf{fat}_{2}(\mathcal{F}_{j^{\prime}})=\mathsf{fat}_{2}(\mathcal{F})$,
then $j^{\prime}=j+1$. Let $j^{*}$ be the minimal $j$ such that
$\mathsf{fat}_{2}(\mathcal{F}_{j})=\mathsf{fat}_{2}(\mathcal{F})$ (if such a
$j$ exists, if not let $j^{*}=0$) and notice that for
$j\not\in\\{j^{*},j^{*}+1\\}$, it hold that
$\mathsf{fat}_{2}(\mathcal{F}_{j})\leq\mathsf{fat}_{2}(\mathcal{F})-1$.

Fix $0<p<1$ to be determined later and construct
$\mu_{{\boldsymbol{z}},\mathcal{F}}$ by sampling
$\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}+1/2}$ with probability $1-p$, and
sampling $\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j}$ with probability
$\frac{p}{m-1}$ for all other $j$. We claim that with an appropriate choice of
$p$, the above construction yields a $\frac{2}{3}$-fractional cover of the
correct size.

In order to prove the claim, for a depth $n$ binary tree ${\boldsymbol{z}}$,
let

$\phi(k,\mathcal{F},{\boldsymbol{z}})=\min_{\begin{subarray}{c}f\in\mathcal{F}\\\
\varepsilon\in\\{\pm
1\\}^{n}\end{subarray}}\mu\left(\left\\{{\boldsymbol{v}}\colon\sum_{t=0}^{n}\mathbf{1}_{\left\\{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
1\right\\}}\leq k\right\\}\right)$ (89)

and let

$\phi(k,d,n)=\min_{\begin{subarray}{c}\mathsf{fat}_{2}(\mathcal{F})\leq d\\\
\text{depth of }{\boldsymbol{z}}\leq
n\end{subarray}}\phi(k,\mathcal{F},{\boldsymbol{z}}).$ (90)

We claim (and prove as Lemma 24 at the conclusion of this proof so as not to
interrupt the argument) that

$\phi(k,d,n)\geq(1-p)^{n+1+k}\left(\frac{p}{m-1}\right)^{d}\binom{k+d}{d}\geq(1-p)^{n+1+k}\left(\frac{p}{m}\right)^{d}\left(\frac{k}{d}\right)^{d}$
(91)

for all $0<p<1$, where the second inequality comes from the elementary lower
bound $\binom{n}{k}\geq(n/k)^{k}$. Now, letting $k=\delta n$ for
$\delta=\frac{7}{36m^{2}}<1$ and $p=\frac{d}{n}$, we note that for $n\geq 2d$,

$\phi(k,d,n)\geq\left(1-\frac{d}{n}\right)^{2n}\left(\frac{d}{mn}\frac{\delta
n}{d}\right)^{d}\geq c\left(\frac{e^{2}\delta}{dm}\right)^{d}.$ (92)

Note that as
${\boldsymbol{v}}_{t}(\varepsilon),f({\boldsymbol{z}}_{t}(\varepsilon))\in\left\\{0,\dots,m,j^{*}+\frac{1}{2}\right\\}$,
if
$\left|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))\right|<1$,
then it is at most $\frac{1}{2}$. Thus, if

$\sum_{t=0}^{n}\mathbf{1}_{\left\\{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
1\right\\}}\leq\delta n$ (93)

then

$\left|\left|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))\right|\right|^{2}=\sum_{t=1}^{n}({\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon)))^{2}\leq
m^{2}\delta n+\frac{1}{2}(1-\delta)n.$ (94)

Recall that $\delta=\frac{7}{36m^{2}}$ and this concludes the proof. ∎

We now prove the technical lemma used above:

######  Lemma 24.

Let $\phi(k,d,n)$ be as defined in the above proof. Then for all $0<p<1$, and
$n\geq-1$ (where $n=-1$ corresponds to an empty tree),

$\phi(k,d,n)\geq(1-p)^{n+1+k}\left(\frac{p}{m-1}\right)^{d}\binom{k+d}{d}$
(95)

###### Proof.

We prove the result by induction on $n$. If $n=-1$ then the left hand side of
(95) equals $1$, while the right hand side equals

$(1-p)^{k}\left(\frac{p}{m-1}\right)^{d}\binom{k+d}{d}\leq(1-p)^{k}p^{d}\binom{k+d}{d}\leq\sum_{\ell=0}^{k+d}(1-p)^{k+d-\ell}p^{\ell}\binom{k+d}{\ell}\\\
=((1-p)+p)^{k+d}=1.$

Thus, we may assume that $n\geq 0$. We prove the following recursive formula:

$\phi(k,d,n)\geq\min\begin{pmatrix}(1-p)\phi(k,d,n-1),\\\
\begin{cases}(1-p)\phi(k-1,d,n-1)+\frac{p}{m-1}\phi(k,d-1,n-1)&\text{if
}k,d>0\\\ \frac{p}{m-1}\phi(k,d-1,n-1)&\text{if }k=0,d>0\\\
\infty&ifd=0\end{cases}\end{pmatrix}$ (96)

To see this, consider a fixed $f,\varepsilon$. We divide into cases:

### If $f({\boldsymbol{z}}_{0})\in\\{j^{*},j^{*}+1\\}$.

Recall that $\mu_{{\boldsymbol{z}},\mathcal{F}}$ samples
$\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}+1/2}$ with probability $1-p$. For any
${\boldsymbol{v}}\in\mathrm{support}(\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}+1/2})$
it holds that ${\boldsymbol{v}}_{0}=j^{*}+1/2$ and so
$\left|{\boldsymbol{v}}_{0}-f({\boldsymbol{z}}_{0})\right|\leq\frac{1}{2}<1$.
Hence,

$\mu_{{\boldsymbol{z}},\mathcal{F}}\left(\left\\{{\boldsymbol{v}}\colon\sum_{t=0}^{n}\mathbf{1}_{\left\\{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
1\right\\}}\leq k\right\\}\right)\\\
\geq(1-p)\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}+1/2}\left(\left\\{{\boldsymbol{v}}\colon\sum_{t=0}^{n}\mathbf{1}_{\left\\{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
1\right\\}}\leq k\right\\}\right)\geq(1-p)\phi(k,d,n-1).$

### If $f({\boldsymbol{z}}_{0})=j\not\in\\{j^{*},j^{*}+1\\}$ and $k,d>0$.

Here, differently from the previous case, for
${\boldsymbol{v}}\in\mathrm{support}(\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}+1/2})$
it holds that $\left|{\boldsymbol{v}}_{0}-f({\boldsymbol{z}}_{0})\right|\geq
1$. Additionally, recall that $\mu_{{\boldsymbol{z}},\mathcal{F}}$ samples
$\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j}$ with probability $\frac{p}{m-1}$.
For any
${\boldsymbol{v}}\in\mathrm{support}(\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j})$,
it holds that ${\boldsymbol{v}}_{0}=f({\boldsymbol{z}}_{0})$. Further, recall
that $\mathsf{fat}_{2}(\mathcal{F}_{j})\leq\mathsf{fat}_{2}(\mathcal{F})-1$.
Hence, we see that in this case,

$\mu_{{\boldsymbol{z}},\mathcal{F}}\left(\left\\{{\boldsymbol{v}}\colon\sum_{t=0}^{n}\mathbf{1}_{\left\\{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
1\right\\}}\leq
k\right\\}\right)\geq(1-p)\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}+1/2}\left(\left\\{{\boldsymbol{v}}\colon\sum_{t=0}^{n}\mathbf{1}_{\left\\{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
1\right\\}}\leq k\right\\}\right)\\\
+\frac{p}{m-1}\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j}\left(\left\\{{\boldsymbol{v}}|\sum_{t=0}^{n}\mathbf{1}_{\left\\{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
1\right\\}}\leq k\right\\}\right)\\\
\geq(1-p)\phi(k-1,d,n-1)+\frac{p}{m-1}\phi(k,d-1,n-1).$

### If $f({\boldsymbol{z}}_{0})=j\not\in\\{j^{*},j^{*}+1\\}$ and $k=0,d>0$.

Similarly to the previous case, we have

$\mu_{{\boldsymbol{z}},\mathcal{F}}\left(\left\\{{\boldsymbol{v}}\colon\sum_{t=0}^{n}\mathbf{1}_{\left\\{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
1\right\\}}\leq
k\right\\}\right)\geq\frac{p}{m-1}\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j}\left(\left\\{{\boldsymbol{v}}|\sum_{t=0}^{n}\mathbf{1}_{\left\\{|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
1\right\\}}\leq k\right\\}\right)\\\ \geq\frac{p}{m-1}\phi(k,d-1,n-1).$

### If $f({\boldsymbol{z}}_{0})=j\not\in\\{j^{*},j^{*}+1\\}$ and $d=0$.

This case cannot hold. Assume that it does towards contradiction. Since
$f({\boldsymbol{z}}_{0})=j\not\in\\{j^{*},j^{*}+1\\}$, we have
$\mathsf{fat}_{2}(\mathcal{F}_{j})\leq\mathsf{fat}_{2}(\mathcal{F})-1=-1$,
which derives the contradiction since the fat numbers are nonnegative.

Thus we have shown (96). We divide into cases. If the minimum in the right
hand side of (96) equals $(1-p)\phi(k,d,n-1)$ then the claim trivially follows
by induction hypothesis. Otherwise, we divide into cases according to $d,k$.
If $k,d>0$ then

$\phi(k,d,n)\geq(1-p)\phi(k-1,d,n-1)+\frac{p}{m-1}\phi(k,d-1,n-1)\\\
\geq(1-p)^{n+k+1}\left(\frac{p}{m-1}\right)^{d}\left(\binom{k+d-1}{d}+\binom{k+d-1}{d-1}\right)=(1-p)^{n+k+1}\left(\frac{p}{m-1}\right)^{d}\binom{k+d}{d}.$

If $k=0,d>0$, we have

$\phi(k,d,n)\geq\frac{p}{m-1}\phi(k,d-1,n-1)\\\
\geq(1-p)^{n+1}\left(\frac{p}{m-1}\right)^{d}\binom{d-1}{d-1}=(1-p)^{n+1}\left(\frac{p}{m-1}\right)^{d}\binom{d}{d},$

as required. Lastly, the case $d=0$ cannot hold, as we assumed that the
minimum in the right hand side of (96) doe not equal $(1-p)\phi(k,d,n-1)$.
This concludes the proof. ∎ Using Proposition 14, we can bound the fractional
covering number of a real valued function class, with respect to its fat-
shattering dimension. We introduce some notation. For any $\alpha>0$ and
function class $\mathcal{F}$ taking values in the unit interval, let
$\lfloor\mathcal{F}\rfloor_{\alpha}$ be the $\frac{\alpha}{2}$-discretization
of $f$, i.e., for any $f\in\mathcal{F}$, let $\lfloor
f\rfloor_{\alpha}=\frac{\alpha}{2}\left\lfloor\frac{2f}{\alpha}\right\rfloor$.
Let $\mathcal{G}=\frac{1}{\alpha}\lfloor\mathcal{F}\rfloor_{\alpha}$. We have
the following lemma, reproven for the sake of completeness:

######  Lemma 25 (Rakhlin et al. , (2015)).

With the notation as above, we have
$\mathsf{fat}_{2}(\mathcal{G})\leq\mathsf{fat}_{\alpha}(\mathcal{F})$.

###### Proof.

Multiplying by $\alpha$, the statement is equivalent to
$\mathsf{fat}_{2\alpha}(\lfloor\mathcal{F}\rfloor_{\alpha})\leq\mathsf{fat}_{\alpha}(\mathcal{F})$.
Let $\mathbf{w}$ be a tree that shatters $\lfloor\mathcal{F}\rfloor_{\alpha}$
at scale $\alpha$ of depth $r$. By definition, there exists a tree
$\mathbf{s}$ such that for all $\varepsilon\in\\{\pm 1\\}^{r}$, there is an
$f\in\mathcal{F}$ such that for all $1\leq t\leq r$

$\varepsilon_{t}\left(\lfloor
f(\mathbf{w}_{t}(\varepsilon)\rfloor_{\alpha}-\mathbf{s}_{t}(\varepsilon)\right)\geq\alpha$
(97)

Note that by construction, $\left|\lfloor
f\rfloor_{\alpha}-f\right|\leq\frac{\alpha}{2}$. Thus for this
$f\in\mathcal{F}$,

$\displaystyle\varepsilon_{t}\left(f(\mathbf{w}_{t}(\varepsilon)-\mathbf{s}_{t}(\varepsilon)\right)$
$\displaystyle\geq\varepsilon_{t}\left(f(\mathbf{w}_{t}(\varepsilon)-\lfloor
f(\mathbf{w}_{t}(\varepsilon)\rfloor_{\alpha}\right)+\varepsilon_{t}\left(\lfloor
f(\mathbf{w}_{t}(\varepsilon)\rfloor_{\alpha}-\mathbf{s}_{t}(\varepsilon)\right)$
(98) $\displaystyle\geq\alpha-\frac{\alpha}{2}\geq\frac{\alpha}{2}$ (99)

Thus ${\boldsymbol{z}}$ also shatters $\mathcal{F}$ at scale $\alpha$. ∎

We are now ready to prove Theorem 13:

###### Proof of Theorem 13.

We claim that for $\alpha=\frac{6}{7}\delta$ and with the notation defined
above, $N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})\leq
N^{\prime}\left(\mathcal{G},\frac{2}{3},{\boldsymbol{z}}\right)$. To see this,
note that if ${\boldsymbol{v}}$ such that
$\left|\left|{\boldsymbol{v}}(\varepsilon)-\lfloor
f\rfloor_{\alpha}({\boldsymbol{z}}(\varepsilon))\right|\right|\leq\frac{4}{7}\delta
n$, then we see that the triangle inequality implies

$\left|\left|{\boldsymbol{v}}(\varepsilon)-f({\boldsymbol{z}}(\varepsilon)\right|\right|\leq\left|\left|{\boldsymbol{v}}(\varepsilon)-\lfloor
f\rfloor_{\alpha}({\boldsymbol{z}}(\varepsilon))\right|\right|+\left|\left|f({\boldsymbol{z}}(\varepsilon))-\lfloor
f\rfloor_{\alpha}({\boldsymbol{z}}(\varepsilon))\right|\right|\leq\frac{4}{7}\delta
n+\frac{3}{7}\delta n=\delta n$ (100)

Thus if $\mu$ is a $\frac{4}{7}\delta$ fractional cover on
$\lfloor\mathcal{F}\rfloor_{\alpha}$, then it is a $\delta$-cover on
$\mathcal{F}$ for $\alpha=\frac{6}{7}\delta$. Scaling by
$\alpha=\frac{6}{7}\delta$ shows that if
$N^{\prime}\left(\lfloor\mathcal{F}\rfloor_{\alpha},\frac{4}{7}\delta,{\boldsymbol{z}}\right)=N^{\prime}\left(\mathcal{G},\frac{2}{3},{\boldsymbol{z}}\right)$.
Now, by construction, $\mathcal{G}$ takes values in
$\left\\{0,1,\dots,\left\lfloor\frac{2}{\alpha}\right\rfloor\right\\}$. Thus,
setting $m=\frac{2}{\alpha}=\frac{7}{3\delta}$ and applying Proposition 14
gives

$N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})\leq
N^{\prime}\left(\mathcal{G},\frac{2}{3},{\boldsymbol{z}}\right)\leq
C\left(\frac{36e}{7}\left(\frac{7}{3\delta}\right)^{3}\right)^{\mathsf{fat}_{2}(\mathcal{G}}\leq
C\left(\frac{4e}{147\delta^{3}}\right)^{\mathsf{fat}_{\frac{6}{7}\delta}(\mathcal{F})}$
(101)

as desired. ∎

##  Appendix C Proof of Proposition 15

We start by proving Proposition 16. We first consider the case
$\mathcal{Y}=\\{1,\dots,m\\}$ and prove:

######  Proposition 26.

Suppose that $\mathcal{F}$ is a collection of functions from $\mathcal{Z}$ to
$\mathcal{Y}=\\{1,\dots,m\\}$ and $\delta\geq 2$. Then

$N^{\prime}(\mathcal{F},\delta)\leq\prod_{i=1}^{\log
m}\left(\frac{C^{i}}{\delta}\right)^{\mathsf{fat}_{2^{i}}(\mathcal{F})},$
(102)

where $C>0$ is a universal constant.

Below, we present the proof of Proposition 26 and then we prove Proposition 16
and finally Proposition 15. First, we can assume that $m$ is an integer power
of $2$. Given a tree ${\boldsymbol{z}}$ and a concept class $\mathcal{F}$, we
construct the fractional cover $\mu=\mu_{{\boldsymbol{z}},\mathcal{F}}$
inductively. We define $\mu$ to be a sub-probability distribution, namely,
each element has a non-negative measure and the sum of measures is at most
$1$. By normalizing $\mu$, one can derive a proper probability measure.

Suppose we have a binary tree ${\boldsymbol{z}}$. If ${\boldsymbol{z}}$ is an
empty tree then $\mu_{{\boldsymbol{z}},\mathcal{F}}$ has a unit mass on the
empty tree. Otherwise, define by ${\boldsymbol{z}}_{0}$,
${\boldsymbol{z}}^{(-1)}$ and ${\boldsymbol{z}}^{(1)}$ its root and left and
right sub-trees, respectively (if the tree has depth zero then
${\boldsymbol{z}}^{(\pm 1)}$ are empty trees). For any concept-class
$\mathcal{G}$, define by $\mu_{{\boldsymbol{z}},\mathcal{G},i}$ the measure on
$\mathcal{Y}$-valued trees ${\boldsymbol{v}}$ such that the root is labeled by
$i$ almost surely and the left and right sub-trees are sampled independently
from $\mu_{{\boldsymbol{z}}^{(-1)},\mathcal{G}}$ and
$\mu_{{\boldsymbol{z}}^{(1)},\mathcal{G}}$.

Define
$\mathcal{F}_{j}=\left\\{f\in\mathcal{F}:f({\boldsymbol{z}}_{0})=j\right\\}$
for $j\in[m]$. For $j=1,\dots,m$ denote

$i(j)=\max\\{i\colon 1\leq
i\leq\log_{2}m,\mathsf{fat}_{2^{i}}(\mathcal{F}_{j})<\mathsf{fat}_{2^{i}}(\mathcal{F})\\}$

with $i(j)=0$ if
$\mathsf{fat}_{2^{i}}(\mathcal{F}_{j})=\mathsf{fat}_{2^{i}}(\mathcal{F})$ for
all $i$. Let $j^{*}$ be an (arbitrarily chosen) minimizer of $i(j)$.

We define $\mu_{{\boldsymbol{z}},\mathcal{F}}$. which is parametrized by some
parameter $p$ to be set later, as follows: For any binary tree
${\boldsymbol{v}}$, define

$\mu_{{\boldsymbol{z}},\mathcal{F}}(v)=(1-p)\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}}(v)+\sum_{j=1}^{m}\lambda_{j}\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j}(v),\quad\text{where
}\lambda_{j}=4^{-i(j)-1}p.$

Observe that the first measure in the sum,
$\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}}$, corresponds to the class
$\mathcal{F}$ while the remaining measures,
$\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j}$ for $j\in[m]$, correspond to the
restricted concept classes $\mathcal{F}_{j}$. Second, note that the sum of
mixture coefficients, $1-p+\sum_{j}\lambda_{j}$, does not necessarily equal
$1$. Since, we define a sub-probability measure, it suffices to show that this
sum is upper bounded by $1$. To do this, we use Lemma 23 from Appendix B.

By Lemma 23, there are at most $2^{i+1}$ classes with $i(j)=i$, hence,

$1-p+\sum_{j=1}^{m}\lambda_{j}\leq 1-p+\sum_{i=0}^{\log_{2}m}|\\{j\colon
i(j)=i\\}|\frac{p}{4^{i+1}}\leq
1-p+\sum_{i=0}^{\log_{2}m}\frac{2^{i+1}p}{4^{i+1}}=1-p+\sum_{i=0}^{\log_{2}m}\frac{p}{2^{i+1}}\leq
1,$

which implies that we defined a sub-probability distribution as required.

We claim that with an appropriate choice of $p$, the above construction yields
a $\delta$-fractional cover of the correct size. In order to prove the claim,
we introduce some notation. For a depth $n$ binary tree ${\boldsymbol{z}}$, a
vector $\overrightarrow{k}=(k_{1},\dots,k_{\log_{2}m})$ a concept class
$\mathcal{F}$, a function $f$ and a path $\varepsilon$, denote the following
set of $[m]$-labelled trees that contains all trees that are close to $f(z)$
on some path $\varepsilon$, where the closeness is measured with respect to
$\overrightarrow{k}$:

$E(\overrightarrow{k},f,\varepsilon,z)=\left\\{{\boldsymbol{v}}\colon\forall
i=1,\dots,\log_{2}m,|\\{t\colon 0\leq t\leq
n,|{\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon))|\geq
2^{i}\\}|\leq\sum_{i^{\prime}=i}^{\log_{2}m}k_{i^{\prime}}\right\\}.$

As we shall show later, for all ${\boldsymbol{v}}\in
E(\overrightarrow{k},f,\varepsilon,z)$ it holds that
$\|{\boldsymbol{v}}(\varepsilon)-f({\boldsymbol{z}}(\varepsilon))\|_{2}^{2}\leq
C\sum_{i}4^{i}k_{i}/n$. Next, we define:

$\phi(\overrightarrow{k},\mathcal{F},{\boldsymbol{z}})=\min_{\begin{subarray}{c}f\in\mathcal{F}\\\
\varepsilon\in\\{\pm
1\\}^{n}\end{subarray}}\mu\left(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}})\right)$
(103)

Where $\mu$ is as constructed above. Notice that
$\phi(\overrightarrow{k},\mathcal{F},{\boldsymbol{z}})$ can be used to bound
the fractional covering numbers of $\mathcal{F}$, since
$E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}})$ contains trees that
approximate $f$ on $\varepsilon$. Lastly, for a vector
$\overrightarrow{d}=(d_{1},\dots,d_{\log_{2}m})$, the following definition
bounds the minimal value of $\varphi$ taken over concept-classes $\mathcal{F}$
whose fat covering numbers are bounded in terms of $\overrightarrow{d}$, as
defined below:

$\varphi(\overrightarrow{k},\overrightarrow{d},n)=\min_{\begin{subarray}{c}\mathcal{F},{\boldsymbol{z}}\colon\\\
\forall i=1,\dots,\log_{2}m,\mathsf{fat}_{2^{i}}(\mathcal{F})\leq d_{i}\\\
\text{depth of }z\leq
n\end{subarray}}\phi(\overrightarrow{k},\mathcal{F},{\boldsymbol{z}}).$ (104)

Here, $n\geq-1$ where $n=-1$ corresponds to the empty tree. Define $e_{i}$ as
the vector with $1$ in coordinate $i$ and zeros otherwise. One can prove the
following inductive formula:

######  Lemma 27.

For any $n\geq 0$,

$\varphi(\overrightarrow{k},\overrightarrow{d},n)\geq\min_{i=0,\dots,\log_{2}m}\varphi_{i}(\overrightarrow{k},\overrightarrow{d},n).$

where
$\varphi_{0}(\overrightarrow{k},\overrightarrow{d},n)=(1-p)\varphi(\overrightarrow{k},\overrightarrow{d},n-1)$
and for all $i=1,\dots,\log_{2}m$

$\varphi_{i}(\overrightarrow{k},\overrightarrow{d},n)=\begin{cases}4^{-i-1}p\varphi(\overrightarrow{k},\overrightarrow{d}-e_{i},n)+(1-p)\varphi(\overrightarrow{k}-e_{i},\overrightarrow{d},n-1)&k_{i},d_{i}>0\\\
4^{-i-1}p\varphi(\overrightarrow{k},\overrightarrow{d}-e_{i},n)&k_{i}=0,d_{i}>0\\\
\infty&d_{i}=0\end{cases}.$

###### Proof.

Fix ${\boldsymbol{z}}$ and $\mathcal{F}$ such that
$\mathsf{fat}_{2^{i}}(\mathcal{F})\leq d_{i}$ for all $i$. Fix $f$ and
$\varepsilon$, denote $j=f({\boldsymbol{z}}_{0})$. We would like to argue that
$\mu(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))\geq\varphi_{i(j)}(\overrightarrow{k},\overrightarrow{d},n)$.
For any tree ${\boldsymbol{v}}$, denote by ${\boldsymbol{v}}^{(\varepsilon)}$
the sub-tree of ${\boldsymbol{v}}$, rooted by a child of the root of
${\boldsymbol{v}}$, that contains the sub-path $\varepsilon_{1:n}$. To derive
the proof, we divide into cases:

  1. 1.

If $i(j)=0$: This follows from the fact that $|j-j^{*}|<2^{i(j)+1}=2$ and from
the definition of $E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}})$, one
has:

$E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}})\supseteq\\{{\boldsymbol{v}}\colon{\boldsymbol{v}}^{(\varepsilon)}\in
E(\overrightarrow{k},f,\varepsilon_{1:n},{\boldsymbol{z}}^{(\varepsilon)}),\mathrm{root}({\boldsymbol{v}})=j^{*}\\}.$
(105)

As a consequence,

$\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}}(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))\geq\mu_{{\boldsymbol{z}}^{(\varepsilon)},\mathcal{F}}(E(\overrightarrow{k},f,\varepsilon_{1:n},{\boldsymbol{z}}^{(\varepsilon)}))\geq\phi(\overrightarrow{k},\mathcal{F},{\boldsymbol{z}}^{(\varepsilon)}).$
(106)

Therefore,

$\displaystyle\mu(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))$
$\displaystyle\geq(1-p)\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}}(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))$
(107)
$\displaystyle\geq(1-p)\phi(\overrightarrow{k},\mathcal{F},{\boldsymbol{z}}^{(\varepsilon)})$
(108)
$\displaystyle\geq(1-p)\varphi(\overrightarrow{k},\overrightarrow{d},n-1)$
(109) $\displaystyle=\varphi_{0}(\overrightarrow{k},\overrightarrow{d},n).$
(110)

  2. 2.

If $i(j)>0$ and $k_{i(j)},d_{i(j)}>0$: First, notice that

$E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}})\supseteq\\{{\boldsymbol{v}}\colon{\boldsymbol{v}}^{(\varepsilon)}\in
E(\overrightarrow{k},f,\varepsilon_{1:n},{\boldsymbol{z}}^{(\varepsilon)}),\mathrm{root}({\boldsymbol{v}})=j\\}.$
(111)

This implies that

$\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j}(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))\geq\mu_{z^{(\varepsilon)},\mathcal{F}_{j}}(E(\overrightarrow{k},f,\varepsilon_{1:n},{\boldsymbol{z}}^{(\varepsilon)}))\geq\phi(\overrightarrow{k},\mathcal{F}_{j},{\boldsymbol{z}}^{(\varepsilon)}).$
(112)

Further, using the fact that $i(j)>0$, one has

$E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}})\supseteq\\{{\boldsymbol{v}}\colon{\boldsymbol{v}}^{(\varepsilon)}\in
E(\overrightarrow{k}-e_{i(j)},f,\varepsilon_{1:n},{\boldsymbol{z}}^{(\varepsilon)}),\mathrm{root}({\boldsymbol{v}})=j^{*}\\},$
(113)

which implies that

$\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}}(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))\geq\mu_{{\boldsymbol{z}}^{(\varepsilon)},\mathcal{F}}(E(\overrightarrow{k}-e_{i(j)},f,\varepsilon_{1:n},{\boldsymbol{z}}^{(\varepsilon)}))\geq\phi(\overrightarrow{k}-e_{i(j)},\mathcal{F},{\boldsymbol{z}}^{(\varepsilon)}).$
(114)

From (112) and (114),

$\displaystyle\mu(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))$
$\displaystyle\geq(1-p)\mu_{{\boldsymbol{z}},\mathcal{F},j^{*}}(E(\overrightarrow{k}-e_{i(j)},f,\varepsilon,{\boldsymbol{z}}))+4^{-i(j)-1}p\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j}(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))$
$\displaystyle\geq(1-p)\varphi(\overrightarrow{k}-e_{i(j)},\mathcal{F},{\boldsymbol{z}}^{(\varepsilon)})+4^{-i(j)-1}p\phi(\overrightarrow{k},\mathcal{F}_{j},{\boldsymbol{z}}^{(\varepsilon)}).$
(115)

From the definition of $i(j)$, one has that
$\mathsf{fat}_{2^{i(j)}}(\mathcal{F}_{j})<\mathsf{fat}_{2^{i(j)}}(\mathcal{F})$.
Hence, from (115),

$\displaystyle\mu(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))$
$\displaystyle\geq(1-p)\varphi(\overrightarrow{k}-e_{i(j)},\overrightarrow{d},n-1)+4^{-i(j)-1}p\varphi(\overrightarrow{k},\overrightarrow{d}-e_{i(j)},n-1)$
(116) $\displaystyle=\varphi_{i(j)}(\overrightarrow{k},\overrightarrow{d},n).$
(117)

  3. 3.

If $i(j)>0$, $k_{i(j)}=0$ and $d_{i(j)}>0$: Using a similar argument as in the
previous case,

$\displaystyle\mu(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))$
$\displaystyle\geq
4^{-i(j)-1}p\mu_{{\boldsymbol{z}},\mathcal{F}_{j},j}(E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}}))\geq
4^{-i(j)-1}p\phi(\overrightarrow{k},\mathcal{F}_{j},{\boldsymbol{z}}^{(\varepsilon)})$
$\displaystyle\geq
4^{-i(j)-1}p\varphi(\overrightarrow{k},\overrightarrow{d}-e_{i(j)},n-1)=\varphi_{i(j)}(\overrightarrow{k},\overrightarrow{d},n).$

  4. 4.

If $i(j)>0$ and $d_{i(j)}=0$: this cannot hold, since
$0\leq\mathsf{fat}_{2^{i(j)}}(\mathcal{F}_{j})<\mathsf{fat}_{2^{i(j)}}(\mathcal{F})\leq
d_{i(j)}$.

∎

We proceed with bounding
$\varphi(\overrightarrow{k},\overrightarrow{d},\overrightarrow{n})$:

######  Lemma 28.

Let $\phi(\overrightarrow{k},\overrightarrow{d},n)$ be as defined in the above
proof. Then for all $0<p<1$, $n\geq-1$ and
$k_{1},\dots,k_{\log_{2}m},d_{1},\dots,d_{\log_{2}m}\geq 0$,

$\displaystyle\phi(\overrightarrow{k},\overrightarrow{d},n)$
$\displaystyle\geq(1-p)^{n+1+\sum_{i=1}^{\log_{2}m}k_{i}}\prod_{i=1}^{\log_{2}m}\left(\frac{p}{4^{i+1}}\right)^{d_{i}}\binom{k_{i}+d_{i}}{d_{i}}.$
(118)

###### Proof.

We prove the result by induction on $n$. For the base of induction, we assume
that $n=-1$. Then the left hand side of (118) equals $1$, while the right hand
side is at most $1$, as follows from the following argument: For all $i$,

$\displaystyle(1-p)^{k_{i}}\left(\frac{p}{4^{i+1}}\right)^{d_{i}}\binom{k_{i}+d_{i}}{d_{i}}$
$\displaystyle\leq(1-p)^{k_{i}}p^{d_{i}}\binom{k_{i}+d_{i}}{d_{i}}$ (119)
$\displaystyle\leq\sum_{\ell=0}^{k_{i}+d_{i}}(1-p)^{k_{i}+d_{i}-\ell}p^{\ell}\binom{k_{i}+d_{i}}{\ell}$
(120) $\displaystyle=((1-p)+p)^{k_{i}+d_{i}}=1.$ (121)

For $n\geq 0$, we would like to lower bound
$\varphi_{i}(\overrightarrow{k},\overrightarrow{d},n)$ by the right hand side
of (118), for all $i=0,\dots,\log n$. First, for $i=0$, this follows directly
from the induction hypothesis. For $i\geq 1$, divide into cases. First, assume
that $k_{i},d_{i}>0$. Then, by induction hypothesis

$\displaystyle\varphi_{i}(\overrightarrow{k},\overrightarrow{d},n)$
$\displaystyle=\frac{p}{4^{i+1}}\varphi(\overrightarrow{k},\overrightarrow{d}-e_{i},n)+(1-p)\varphi(\overrightarrow{k}-e_{i},\overrightarrow{d},n-1)$
$\displaystyle\geq(1-p)^{n+\sum_{i^{\prime}\neq
i}k_{i^{\prime}}}\prod_{i^{\prime}\neq
i}\left(\frac{p}{4^{i^{\prime}+1}}\right)^{d_{i^{\prime}}}\binom{k_{i^{\prime}}+d_{i^{\prime}}}{d_{i^{\prime}}}\cdot$
$\displaystyle\left(\frac{p}{4^{i+1}}\cdot(1-p)^{k_{i}}\left(\frac{p}{4^{i+1}}\right)^{d_{i}-1}\binom{k_{i}+d_{i}-1}{d_{i}-1}+(1-p)\cdot(1-p)^{k_{i}-1}\left(\frac{p}{4^{i+1}}\right)^{d_{i}}\binom{k_{i}-1+d_{i}}{d_{i}}\right)$
$\displaystyle=(1-p)^{n+1+\sum_{i=1}^{\log_{2}m}k_{i}}\prod_{i=1}^{\log_{2}m}\left(\frac{p}{4^{i+1}}\right)^{d_{i}}\binom{k_{i}+d_{i}}{d_{i}},$

using the equality

$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.$

Next, assume that $k_{i}=0$. Then,

$\displaystyle\varphi_{i}(\overrightarrow{k},\overrightarrow{d},n)$
$\displaystyle=\frac{p}{4^{i+1}}\varphi(\overrightarrow{k},\overrightarrow{d}-e_{i},n)$
$\displaystyle\geq\frac{p}{4^{i+1}}\cdot(1-p)^{n+\sum_{i^{\prime}\neq
i}k_{i^{\prime}}}\prod_{i^{\prime}\neq
i}\left(\frac{p}{4^{i^{\prime}+1}}\right)^{d_{i^{\prime}}}\binom{k_{i^{\prime}}+d_{i^{\prime}}}{d_{i^{\prime}}}\cdot\left(\frac{p}{4^{i+1}}\right)^{d_{i}-1}\binom{d_{i}-1}{d_{i}-1}$
$\displaystyle=\cdot(1-p)^{n+\sum_{i^{\prime}\neq
i}k_{i^{\prime}}}\prod_{i^{\prime}\neq
i}\left(\frac{p}{4^{i^{\prime}+1}}\right)^{d_{i^{\prime}}}\binom{k_{i^{\prime}}+d_{i^{\prime}}}{d_{i^{\prime}}}\cdot\left(\frac{p}{4^{i+1}}\right)^{d_{i}}\binom{d_{i}}{d_{i}}$
$\displaystyle=(1-p)^{n+1+\sum_{i=1}^{\log_{2}m}k_{i}}\prod_{i=1}^{\log_{2}m}\left(\frac{p}{4^{i+1}}\right)^{d_{i}}\binom{k_{i}+d_{i}}{d_{i}}.$

Lastly, assume that $d_{i}=0$. Then,
$\varphi_{i}(\overrightarrow{k},\overrightarrow{d},n)=\infty$, and the
statement holds as well. ∎

###### Proof of Proposition 26.

Define $k_{i}=8^{-i}\delta n$ for $i=1,\dots,\log_{2}n$ and notice that it
suffices to show that

$\varphi(\overrightarrow{k},\overrightarrow{d},n)\geq\prod_{i=1}^{\log_{2}m}\left(c^{i}\delta\right)^{\mathsf{fat}_{2^{i}}(\mathcal{F})}.$

Indeed, for any $f,\varepsilon$, and any ${\boldsymbol{v}}\in
E(\overrightarrow{k},f,\varepsilon,{\boldsymbol{z}})$, it holds that

$\|{\boldsymbol{v}}(\varepsilon)-f({\boldsymbol{z}}(\varepsilon))\|_{2}=\sqrt{\frac{1}{n+1}\sum_{t=0}^{n}({\boldsymbol{v}}_{t}(\varepsilon)-f({\boldsymbol{z}}_{t}(\varepsilon)))^{2}}\leq
C\delta,$

for some universal constant $C>0$. This implies that the lower bound on
$\varphi(\overrightarrow{k},\overrightarrow{d},n)$ can be directly translated
to an upper bound on the fractional $\ell_{2}$ covering numbers.

Applying Lemma 28 with the parameter $p=d_{1}/n$, using
$d_{1}=\mathsf{fat}_{2}(\mathcal{F})\geq\mathsf{fat}_{2^{i}}(\mathcal{F})=d_{i}$
for all $i\geq 1$ and using the inequality $\binom{n}{k}\geq(n/k)^{k}$, we
derive that

$\varphi(\overrightarrow{k},\overrightarrow{d},n)\geq(1-\frac{d_{1}}{n})^{2n}\prod_{i=1}^{\log
n}\left(\frac{d_{1}}{4^{i+1}n}\right)^{d_{i}}\left(\frac{k_{i}}{d_{i}}\right)^{d_{i}}\geq
ce^{-2d_{1}}\prod_{i=1}^{\log n}\left(\frac{\delta}{4\cdot
32^{i}}\right)^{d_{i}},$

as required. ∎

Using Proposition 26, we can bound the fractional covering number of a real
valued function class, with respect to its fat-shattering dimension.

###### Proof of Proposition 16.

We apply Lemma 25 and replicate the proof of Theorem 13 found in Appendix B.
With the notation from that section, we note that for any ${\boldsymbol{z}}$
by the results of that proof,

$\displaystyle N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})$
$\displaystyle\leq
N^{\prime}\left(\frac{1}{\alpha}\lfloor\mathcal{F}\rfloor_{\alpha},\frac{\delta}{\alpha}-\frac{1}{2},{\boldsymbol{z}}\right)$
(122)
$\displaystyle\mathsf{fat}_{2}\left(\frac{1}{\alpha}\lfloor\mathcal{F}\rfloor_{\alpha}\right)$
$\displaystyle=\mathsf{fat}_{2\alpha}\left(\lfloor\mathcal{F}\rfloor_{\alpha}\right)\leq\mathsf{fat}_{\alpha}(\mathcal{F})$
(123)

Letting $\alpha=\frac{2}{3}\delta$ and plugging into the result of Proposition
26 gives us

$\displaystyle N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})$
$\displaystyle\leq
N^{\prime}\left(\frac{1}{\alpha}\lfloor\mathcal{F}\rfloor_{\alpha},1,{\boldsymbol{z}}\right)\leq\prod_{i=1}^{\log\frac{c}{\delta}}\left(\frac{C}{\frac{\delta}{\alpha}-\frac{1}{2}}\right)^{\mathsf{fat}_{2^{i}}\left(\frac{1}{\alpha}\lfloor\mathcal{F}\rfloor_{\alpha}\right)}$
(124)
$\displaystyle\leq\prod_{i=1}^{\log\frac{c}{\delta}}C^{\mathsf{fat}_{2^{i}c\delta}(\mathcal{F})}$
(125)

as desired. ∎

###### Proof of Theorem 15.

We start by bounded in $\sqrt{\log N^{\prime}(\mathcal{F},\delta)}$ for a
single value of $\delta$. Taking a logarithm in (32), one obtains

$\log N^{\prime}(\mathcal{F},\delta)\leq
C\sum_{i=1}^{\log(1/\delta)+C^{\prime}}i\cdot\mathsf{fat}_{2^{i}c\delta}(\mathcal{F}).$
(126)

Using the subadditivity of the square root, one obtains:

$\sqrt{\log
N^{\prime}(\mathcal{F},\delta)}\leq\sqrt{C}\sum_{i=1}^{\log(1/\delta)+C^{\prime}}\sqrt{i\cdot\mathsf{fat}_{2^{i}c\delta}(\mathcal{F})}.$
(127)

Each term corresponding to $i$ can be bounded by

$\frac{1}{2^{i-1}c\delta}\int_{x=2^{i-1}c\delta}^{2^{i}c\delta}\sqrt{i\mathsf{fat}_{x}(\mathcal{F})}\leq
2\int_{x=2^{i-1}c\delta}^{2^{i}c\delta}\frac{\sqrt{i\mathsf{fat}_{x}(\mathcal{F})}}{x}\leq
C\int_{x=2^{i-1}c\delta}^{2^{i}c\delta}\frac{\sqrt{\log(Cx/\delta)\mathsf{fat}_{x}(\mathcal{F})}}{x}.$

Hence, we derive that

$\sqrt{\log N^{\prime}(\mathcal{F},\delta)}\leq
C\int_{x=c\delta}^{1}\frac{\sqrt{\log(Cx/\delta)\mathsf{fat}_{x}(\mathcal{F})}}{x}$
(128)

Next, we combine the above bound by taking an integral, and switching the
order of integration:

$\displaystyle\int_{b}^{1}\sqrt{\log N^{\prime}(\mathcal{F},\delta)}d\delta$
$\displaystyle\leq
C\int_{\delta=b}^{1}\int_{x=c\delta}^{1}\frac{\sqrt{\log(x/\delta)\mathsf{fat}_{x}(\mathcal{F})}}{x}dxd\delta$
$\displaystyle=C\int_{x=cb}^{1}\sqrt{\mathsf{fat}_{x}(\mathcal{F})}\int_{\delta=b}^{x/c}\frac{\sqrt{\log(Cx/\delta)}}{x}d\delta
dx$ $\displaystyle\leq
C^{\prime}\int_{x=cb}^{1}\sqrt{\mathsf{fat}_{x}(\mathcal{F})}dx.$

∎

##  Appendix D Miscellaneous Proofs

###### Proof of Proposition 5.

By scaling, it suffices to consider $L=1$. Let $\widetilde{\mu}=\ell_{\\#}\mu$
be the pushforward of $\mu$ by $\ell$. Because $\ell$ is Lipschitz, we note
that $\ell\circ B_{\delta}(f({\boldsymbol{z}}),\varepsilon)\subseteq
B_{\delta}(\ell\circ f({\boldsymbol{z}}),\varepsilon)$. By monotonicity of
measures, we then have

$\sqrt{\log\frac{1}{\widetilde{\mu}(B_{\delta}(\ell\circ
f({\boldsymbol{z}}),\varepsilon))}}\leq\sqrt{\log\frac{1}{\widetilde{\mu}(\ell(B_{\delta}(f({\boldsymbol{z}}),\varepsilon))}}=\sqrt{\log\frac{1}{\mu(B_{\delta}(f({\boldsymbol{z}}),\varepsilon))}}$
(129)

where the equality follows from the definition of the push-forward. The result
follows by taking an infimum over measures $\mu$. ∎

###### Proof of Lemma 7.

Let ${\boldsymbol{v}}_{1},\dots,{\boldsymbol{v}}_{N}$ be a $\delta$-cover and
let $\mu$ be a a measure that takes ${\boldsymbol{v}}_{j}$ with probability
$\frac{1}{N}$. Then by definition of the covering numbers, $\mu$ is a
$\delta$-fractional cover of size $N$. The result follows. ∎

###### Proof of Lemma 8.

The upper bound follows from Lemma 7. Fix a ${\boldsymbol{z}}$. As we are in
the offline world, we have packing-covering duality (see, for example, (van
Handel,, 2014, Lemma 5.12)). Thus, it suffices to show that
$D\left(\mathcal{F},2\delta\right)\leq N^{\prime}(\mathcal{F},\delta)$. To see
this, consider a set of points $x_{1},\dots,x_{N}$ that are $2\delta$-packed
and consider the balls $B_{\delta}(x_{i})$. By definition of a fractional
cover, if $\mu$ is such, then $\mu(B_{\delta}(x_{i}))\geq\frac{1}{\gamma}$ for
all $i$. by the fact that the $x_{i}$ are packed, the sets $B_{\delta}(x_{i})$
are pairwise disjoint and so by additivity of the measure and the fact that it
is a probability measure,

$1\geq\mu\left(\bigcup_{1\leq i\leq N}B_{\delta}(x_{i})\right)\geq
N\mu\left(B_{\delta}(x_{1})\right)\geq\frac{N}{\gamma}$ (130)

the result follows. ∎

###### Proof of Proposition 9.

A majorizing measure is multi-scale, while a fractional cover is single-scale;
to turn the latter into the former, we consider the following mixture
distribution. If the integral of the fractional cover is infinite then there
is nothing to prove; thus, assume that the this quantity is finite. Suppose
$\alpha=0$. Let $\delta_{j}$ be the smallest $\delta$ such that
$N^{\prime}(\mathcal{V},\delta)\leq 2^{2^{j}}$ and let $\mu_{j}$ be an optimal
$\delta_{j}$-fractional cover. Let

$\mu=c\sum_{j}j^{-2}\mu_{j}$ (131)

Note that the above sum is over all $j$ sufficiently large by the assumption
that the integral is finite and we let $c$ be a normalizing constant. Now, we
have for any ${\boldsymbol{v}},\varepsilon$,

$\displaystyle
I_{\mu}({\boldsymbol{v}},\varepsilon)=\int_{0}^{1}\sqrt{\log\frac{1}{\mu(B_{\delta}({\boldsymbol{v}},\varepsilon))}}d\delta\leq\sum_{j}\int_{\delta_{j}}^{\delta_{j-1}}\sqrt{\log\frac{1}{\mu(B_{\delta}({\boldsymbol{v}},\varepsilon))}}d\delta$
(132)

By construction, for any $\delta\geq\delta_{j}$,

$\displaystyle\mu(B_{\delta}({\boldsymbol{v}},\varepsilon))\geq\mu(B_{\delta_{j}}({\boldsymbol{v}},\varepsilon))\geq\frac{1}{j^{2}}\mu_{j}(B_{\delta_{j}}({\boldsymbol{v}},\varepsilon))\geq\frac{1}{j^{2}2^{2^{j}}}\geq\frac{1}{2^{2\times
2^{j}}}$ (133)

Thus we have

$\displaystyle\int_{\delta_{j}}^{\delta_{j-1}}\sqrt{\log\frac{1}{\mu(B_{\delta}({\boldsymbol{v}},\varepsilon))}}d\delta\leq
c\delta_{j-1}2^{\frac{j}{2}}\leq c^{\prime}\delta_{j-1}2^{\frac{j-1}{2}}$
(134)

Thus,

$\displaystyle
I_{\mu}({\boldsymbol{v}},\varepsilon)\leq\sum_{j}c^{\prime}\delta_{j-1}2^{\frac{j-1}{2}}\leq
C\int_{0}^{1}\sqrt{\log N^{\prime}(\mathcal{V},\delta)}d\delta$ (135)

If $\alpha>0$, simply cut off $j$ such that $\delta_{j}\geq\alpha$. The same
technique applies, concluding the proof. ∎

###### Proof of Corollary 11.

By (Rakhlin et al. ,, 2015, Lemma 4), we have for any $x>0$

$\displaystyle\mathbb{P}_{\varepsilon}\left(\sup_{f\in\mathcal{F}}\left|\frac{1}{n}\sum_{t=1}^{n}f(Z_{t})-\mathbb{E}[f(Z_{t})|\mathcal{A}_{t}]\right|\geq
x\right)\leq
4\mathbb{P}_{\varepsilon}\left(\left|\frac{1}{n}\sum_{t=1}^{n}\varepsilon_{t}f({\boldsymbol{z}}_{t}(\varepsilon))\right|\right)$
(136)

By Theorem 10, we can control the right hand side of (136) and conclude the
proof. ∎

###### Proof of Corollary 18.

The upper bound follows immediately from setting $\alpha=0$ in the second
statement of Theorem 10 and then bounding the resulting integral by
Proposition 15.

For the lower bound, we first need to show that if $\mathcal{F}$ is
$(c,p)$-bounded, then

$\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta\leq\frac{2\sqrt{c}}{1-2^{\frac{p}{2}-1}}$
(137)

To do this, we note that the function
$\delta\mapsto\mathsf{fat}_{\delta}(\mathcal{F})$ is monotone non-increasing.
Thus we have

$\displaystyle\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta$
$\displaystyle=\sum_{j=1}^{\infty}\int_{2^{-j}}^{2^{-j+1}}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta\leq\sum_{j=1}^{\infty}2^{-j}\sqrt{\mathsf{fat}_{2^{-j}}(\mathcal{F})}$
(138)
$\displaystyle\leq\sum_{j=1}^{\infty}2^{-j}\sqrt{c2^{jp}}\leq\frac{2\sqrt{c}}{1-2^{\frac{p}{2}-1}}$
(139)

Now, noting that $\mathsf{fat}_{1}(\mathcal{F})\geq 1$, we see that the above
implies that for any $\alpha<1$,

$\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta\leq\frac{2\sqrt{c}}{1-2^{\frac{p}{2}-1}}\leq\frac{2\sqrt{c}}{1-2^{\frac{p}{2}-1}}\sup_{\delta>\alpha}\delta\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}$
(140)

Note that the definition of a $(c,p)$-bounded class ensures that the right
hand side of Proposition 15 tends to a finite limit as $b\downarrow 0$; call
this finite limit $A$. To get the lower bound, we apply (Rakhlin et al. ,,
2015, Lemma 2), which says that

$\sup_{\delta>0}\delta\sqrt{\frac{\min(\mathsf{fat}_{\delta}(\mathcal{F}),n)}{32}}\leq\sqrt{n}\mathcal{R}_{n}(\mathcal{F})$
(141)

and, moreover, that if $\delta>2\mathcal{R}_{n}(\mathcal{F})$, then
$\mathsf{fat}_{\delta}(\mathcal{F})<n$. Thus, using the upper bound on
$\mathcal{R}_{n}(\mathcal{F})$ just proven, we see that

$\displaystyle\sqrt{n}\mathcal{R}_{n}(\mathcal{F})$ $\displaystyle\geq
C^{\prime}\sup_{\delta>2\mathcal{R}_{n}(\mathcal{F})}\delta\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}\geq
C^{\prime}\sup_{\delta>\frac{c^{\prime}}{\sqrt{n}}\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta}\delta\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}$
(142) $\displaystyle\geq
C^{\prime}\sup_{\delta>\frac{c^{\prime}A}{\sqrt{n}}}\delta\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}\geq
C^{\prime}\frac{1-2^{\frac{p}{2}-1}}{2\sqrt{c}}\int_{0}^{1}\sqrt{\mathsf{fat}_{\delta}(\mathcal{F})}d\delta$
(143)

The result follows. ∎

###### Proof of Corollary 19.

By scaling it suffices to consider the case $L=1$. By Theorem 10 we have

$\mathcal{R}_{n}(\ell\circ\mathcal{F})\leq\frac{C}{\sqrt{n}}\int_{0}^{1}\sqrt{\log
N^{\prime}(\ell\circ\mathcal{F},\delta,{\boldsymbol{z}})}d\delta$ (144)

It is immediate from the definition of the fractional covering number that
$N^{\prime}(\ell\circ\mathcal{F},\delta,{\boldsymbol{z}})\leq
N^{\prime}(\mathcal{F},\delta,{\boldsymbol{z}})$. Applying Proposition 15 and
Corollary 18 concludes the proof. ∎