# Primal and Dual Combinatorial Dimensions

Pieter Kleer
Tilburg University
Tilburg, The Netherlands
<EMAIL_ADDRESS>Hans Simon
Max Planck Institute for Informatics
Saarland Informatics Campus (SIC)
Saarbrücken, Germany
<EMAIL_ADDRESS>
###### Abstract

We give tight bounds on the relation between the primal and dual of various
combinatorial dimensions, such as the pseudo-dimension and fat-shattering
dimension, for multi-valued function classes. These dimensional notions play
an important role in the area of learning theory. We first review some
(folklore) results that bound the dual dimension of a function class in terms
of its primal, and after that give (almost) matching lower bounds. In
particular, we give an appropriate generalization to multi-valued function
classes of a well-known bound due to Assouad (1983), that relates the primal
and dual VC-dimension of a binary function class.

##  1 Introduction

The Vapnik-Chervonenkis (VC) dimension [11] is a fundamental combinatorial
dimension in learning theory used to characterize the complexity of _learning_
a class $X$ consisting of functions $f:Y\rightarrow\\{0,1\\}$ where $X$ and
$Y$ are given (possibly infinite) sets. Informally, the VC-dimension captures
how rich or complex a class of functions is. Many extensions of the VC-
dimension to multi-valued functions $f:X\rightarrow Z$, for some given
$Z\subseteq\mathbbm{R}$, have been proposed in the literature, such as the
Vapnik-dimension (also known as the uniform pseudo-dimension) [10], the
Pollard-dimension (also known as pseudo-dimension) [9, 5], and the fat-
shattering dimension [6]. All these combinatorial dimensions are formally
defined in Section 2.

Every (primal) class of functions can be identified with a _dual class_ whose
functions are of the form $g_{y}:X\rightarrow Z$ for $y\in Y$ defined by
$g_{y}(f)=f(y)$ for $f\in X$. When interpreting a function class as a matrix
$A$ whose rows and columns are indexed by $X$ and $Y$, respectively, the dual
class is simply given by the transpose matrix $A^{\top}$. The (VC, pseudo-,
etc..) dimension of the dual class is defined as the dimension of the matrix
$A^{T}$.

Assouad [2] showed the following relation between the primal VC-dimension
$\mathrm{VC}(A)$ and the dual VC-dimension $\mathrm{VC}^{*}(A)$:

$\mathrm{VC}^{*}(A)\leq 2^{\mathrm{VC}(A)+1}-1.$ (1.1)

This has turned out to be a very useful inequality, e.g., in the context of
so-called sample compression schemes [8]. In case $\mathrm{VC}^{*}(A)$ is a
power of two, this immediately yields $\mathrm{VC}^{*}(A)\leq
2^{\mathrm{VC}(A)}$. It is known that this bound is tight for all values of
$\mathrm{VC}^{*}(A)$, see, e.g., [7].

The purpose of this work is to understand the relation between the primal and
dual of combinatorial dimensions for multi-valued function classes, in
particular, for multi-valued functions where $Z=\\{0,1,\dots,k\\}$ for
$k\in\mathbb{N}$. For the pseudo-dimension, as explained in Section 3, it can
be shown that

$\mathrm{Pdim}^{*}(A)\leq k\cdot\left(2^{\mathrm{Pdim}(A)+1}-1\right),$ (1.2)

which naturally generalizes Assouad’s bound in (1.1).111We refer to this as a
folklore result, rather than a contribution of this work. Again, when
$\mathrm{Pdim}^{*}(A)$ is a power of two, this yields

$\mathrm{Pdim}^{*}(A)\leq k\cdot 2^{\mathrm{Pdim}(A)}.$ (1.3)

Our first contribution is that the bound in (1.3) is in fact tight for every
value of $k$ and $\mathrm{Pdim}(A)$ (Theorem 4.2). In case
$\mathrm{Pdim}(A)=1$, we give an improved bound of $k+2$ (Theorem 4.1), and
also show that this is tight (Theorem 4.2). We obtain similar bounds for the
fat-shattering dimension (Theorem 4.5).

######  Remark 1.1.

It is sometimes believed that Assouad’s bound also holds for combinatorial
dimensions beyond the VC-dimension, see, e.g., [4]. Our results show that this
is, unfortunately, not correct.

Outline. We continue in Section 2 with all the necessary definitions and
notations, in particular the formal definitions of all combinatorial
dimensions considered in this work. Then, in Section 3, we outline known
results regarding the relations between various combinatorial dimensions and
their duals. After that, in Section 4, we summarize our results, followed by
their proofs in Section 5.

##  2 Preliminaries

For $k\geq 1$, we set $[k]:=\\{1,\ldots,k\\}$ and $[k]_{0}:=[k]\cup\\{0\\}$.
Let $X$ and $Y$ be disjoint sets and let $Z\subseteq\mathbbm{R}$ be a subset
of the reals. Consider a function $A:X\times Y\rightarrow Z$. For $x\in X$, we
define $A_{x}:Y\rightarrow Z$ by $A_{x}(y)=A(x,y)$ and refer to $A_{x}$ as a
_row_ of $A$. For $y\in Y$, we define $A_{y}:X\rightarrow Z$ by
$A_{y}(x)=A(x,y)$ and refer to $A_{y}$ as a _column_ of $A$. The _transpose_
of $A$ is defined as the function $A^{\top}:Y\times X\rightarrow Z$ given by
$A^{\top}(y,x)=A(x,y)$. As suggested by this terminolgy, we view $A$ as a
(possibly infinite) matrix with rows indexed by $X$, columns indexed by $Y$
and with $A^{\top}$ as its transpose.

A matrix $A:X\times Y\rightarrow Z$ with $Z=\\{0,1\\}$ is said to be
_Boolean_. Let $d\geq 1$ be a positive integer. We denote by $B_{d}:X\times
Y\rightarrow\\{0,1\\}$ the Boolean matrix which is defined as follows:

  1. 1.

$X=[2^{d}]$ and $Y=[d]$.

  2. 2.

For every function $b:[d]\rightarrow\\{0,1\\}$, there exists an $x\in[2^{d}]$
such that, for every $y\in[d]$, we have $B_{d}(x,y)=b(y)$.

Note that $B_{d}$ is unique modulo renaming rows and columns.

######  Definition 2.1 (Shattered sets).

Let $A:X\times Y\rightarrow Z$, with $Z\subseteq\mathbb{R}$, be a matrix and
let $J\subseteq Y$ be a subset of its columns.

  1. 1.

Suppose that $Z=\\{0,1\\}$. We say that $J$ is _VC-shattered_ by $A$ if, for
every function $b:J\rightarrow\\{0,1\\}$, there exists an $x\in X$ such that,
for every $y\in J$, we have $B(x,y)=b(y)$.

  2. 2.

We say that $J$ is _P-shattered_ by $A$ if there exists a function
$\mathbf{t}:J\rightarrow\mathbbm{R}$ such that the following holds: for every
function $b:J\rightarrow\\{0,1\\}$, there exists an $x\in X$ such that, for
every $y\in J$, we have $A(x,y)\geq\mathbf{t}(y)$ iff $b(y)=1$.

  3. 3.

Let $\gamma>0$. We say that $J$ is _$P_{\gamma}$ -shattered_ by $A$ if there
exists a function $\mathbf{t}:J\rightarrow\mathbbm{R}$ such that the following
holds: for every function $b:J\rightarrow\\{0,1\\}$, there exists an $x\in X$
such that, for every $y\in J$, we have

$A(x,y)\left\\{\begin{array}[]{ll}\geq\mathbf{t}(y)+\gamma&\mbox{if
$b(y)=1$}\\\ <\mathbf{t}(y)-\gamma&\mbox{if
$b(y)=0$}\end{array}\right.\enspace.$

  4. 4.

We say that $J$ is _V-shattered_ by $A$ if there exists a number
$t\in\mathbbm{R}$ such that the following holds: for every function
$b:J\rightarrow\\{0,1\\}$, there exists an $x\in X$ such that, for every $y\in
J$, we have $A(x,y)\geq t$ iff $b(y)=1$.

  5. 5.

Let $\gamma>0$. We say that $J$ is _$V_{\gamma}$ -shattered_ by $A$ if there
exists a number $t\in\mathbbm{R}$ such that the following holds: for every
function $b:J\rightarrow\\{0,1\\}$, there exists an $x\in X$ such that, for
every $y\in J$, we have

$A(x,y)\left\\{\begin{array}[]{ll}\geq t+\gamma&\mbox{if $b(y)=1$}\\\
<t-\gamma&\mbox{if $b(y)=0$}\end{array}\right.\enspace.$

We will refer to $\mathbf{t}:J\rightarrow\mathbbm{R}$ occuring in the
definition of $P$\- and the $P_{\gamma}$-shattered sets as the _thresholds
used for shattering $J$_. Similarly, we will refer to $t\in\mathbbm{R}$
occuring in the definition of $V$\- and the $V_{\gamma}$-shattered sets as the
_uniform threshold used for shattering $J$_.

######  Definition 2.2 (Combinatorial dimensions).

Let $A:X\times Y\rightarrow Z$ be a matrix. Let
$\tau\in\\{\mathrm{VC},P,P_{\gamma},V,V_{\gamma}\\}$ be one of the shattering
types mentioned in Definition 2.1. The _(primal) $\tau$-dimension_ of $A$ is
the size of a largest set $J\subseteq Y$ that is $\tau$-shattered by $A$
(resp. $\infty$ if there exist $\tau$-shatterable sets of unbounded size). The
_dual $\tau$-dimension_ of $A$ is defined as the $\tau$-dimension of
$A^{\top}$.

We use the notations $\mathrm{VC}(A)$, $\mathrm{Pdim}(A)$,
$\mathrm{P_{\gamma}}(A)$, $\mathrm{Vdim}(A)$ and $\mathrm{V_{\gamma}}(A)$ for
the (primal) dimensions of type $\tau=\mathrm{VC},P,P_{\gamma},V,V_{\gamma}$,
respectively. Here, $\mathrm{VC}(A)$ is the VC-dimension [11],
$\mathrm{Pdim}(A)$ the pseudo-dimension [9, 5], $\mathrm{P_{\gamma}}(A)$ the
fat-shattering dimension [6], $\mathrm{Vdim}(A)$ the Vapnik-dimension [10] and
$\mathrm{V_{\gamma}}(A)$ the fat-shattered version of the Vapnik-dimension,
see, e.g., [1]. The corresponding dual dimensions are denoted by
$\mathrm{VC}^{*}(A)$, $\mathrm{Pdim}^{*}(A)$, $P_{\gamma}^{*}(A)$,
$\mathrm{Vdim}^{*}(A)$ and $V_{\gamma}^{*}(A)$, respectively.

The matrix _obtained by thresholding the columns of $A:X\times Y\rightarrow Z$
at $\mathbf{t}:Y\rightarrow\mathbbm{R}$_ is defined as the Boolean matrix
$B:X\times Y\rightarrow\\{0,1\\}$ such that, for all $x\in X$ and $y\in Y$, we
have $B(x,y)=1$ iff $A(x,y)\geq\mathbf{t}(y)$. For $I\subseteq X$ and
$J\subseteq Y$, we denote the restriction of $A$ to $I\times J$ by $A_{I,J}$.
In other words: $A_{I,J}$ is the submatrix of $A$ whose rows are indexed by
$I$ and whose columns are indexed by $J$. A _witness for the inequality
$\mathrm{Pdim}(A)\geq d$_ is defined as a tripel $(I,J,\mathbf{t})$ such that
the following holds:

  1. 1.

$I$ is a subset of $X$ of size $2^{d}$, $J$ is a subset of $Y$ of size $d$ and
$\mathbf{t}:J\rightarrow\mathbbm{R}$.

  2. 2.

Every pattern $b:J\rightarrow\\{0,1\\}$ occurs in exactly one row of the
Boolean matrix obtained by thresholding the columns of $A_{I,J}$ at
$\mathbf{t}$, i.e., $A_{I,J}$ equals $B_{d}$ up to permutation of its rows.

######  Remark 2.3.

Let $k\geq 1$ be a positive integer. Consider a matrix $A:X\times
Y\rightarrow[k]_{0}$. It is easy to see that, if a set $J\subseteq Y$ can be
$P$-shattered by $A$ with thresholds $\mathbf{t}:J\rightarrow\mathbbm{R}$,
then it can also be $P$-shattered with (suitably chosen) thresholds
$\mathbf{t}:J\rightarrow[k]$. An analogous remark applies to $V$-shattering
with a uniform threshold $t$.

When analyzing the $P$\- or the $V$-dimension of a matrix with entries in
$[k]_{0}$, we will assume that thresholds are taken from $[k]$ whenever we
find that convenient.

##  3 Known relations

In this section we review some known relations between the combinatorial
dimensions defined in Section 2.

###  3.1 Bounding P- in terms of V-dimension

It follows directly from the definitions that

$\mathrm{Vdim}(A)\leq\mathrm{Pdim}(A)\ \mbox{ and
}\mathrm{V_{\gamma}}(A)\leq\mathrm{P_{\gamma}}(A).$ (3.1)

This raises the question whether we can bound the $P$\- in terms of the
$V$-dimension (resp. the $P_{\gamma}$ in terms of the $V_{\gamma}$-dimension).
The gap between $\mathrm{Pdim}(A)$ and $\mathrm{Vdim}(A)$ cannot be bounded in
general, as the following well-known example shows.

######  Example 3.1.

Let $X$ be the set of all monotone222A function $f:[0,1]\rightarrow[0,1]$ is
monotone if $f(x)\leq f(y)$ for all $x\leq y$. functions from $[0,1]$ to
$[0,1]$, $Y=[0,1]$ and $A(x,y)=x(y)$ for $x\in X$. Then $\mathrm{Vdim}(A)=1$
and $\mathrm{Pdim}(A)=\infty$.

In order to bound the $P$\- in terms of the $V$-dimension, the focus will
therefore be on matrices of the form $A:X\times Y\rightarrow[k]_{0}$.
According to the following results of Ben-David et al. [3] (here expressed in
our notation), the $P$\- can exceed the $V$-dimension by factor $k$, but not
by a larger factor333See [3, Theorem 7-8] and the proof of [3, Theorem 7].:

######  Theorem 3.2 ([3]).

For every matrix $A:X\times Y\rightarrow[k]_{0}$, we have

$\mathrm{Pdim}(A)\leq k\cdot\mathrm{Vdim}(A).$ (3.2)

######  Theorem 3.3 ([3]).

For every $d\geq 1$ and every $k\geq 1$, there exists a matrix $A:X\times
Y\rightarrow[k]_{0}$ such that

$\mathrm{Vdim}(A)=d\ \mbox{ and }\ \mathrm{Pdim}(A)=k\cdot d.$

Alon et al. [1] have bounded $P_{\gamma}$\- in terms of the
$V_{\gamma/2}$-dimension.

######  Theorem 3.4 ([1]).

For every matrix $A:X\times Y\rightarrow[0,1]$ and every $0<\gamma\leq 1/2$,
we have444In [3], one finds a factor $2\lceil 1/(2\gamma)\rceil$ at the place
of factor $\lceil 1/\gamma\rceil$. We find the latter (and slightly smaller)
factor preferable because of its simpler form.

$\mathrm{P_{\gamma}}(A)\leq\left(\left\lceil\frac{1}{\gamma}\right\rceil-1\right)\cdot\mathrm{V_{\gamma/2}}(A)\leq\left(\left\lceil\frac{1}{\gamma}\right\rceil-1\right)\cdot\mathrm{Pdim}(A)\enspace.$
(3.3)

###### Proof.

The thresholds $t_{1},\ldots,t_{d}$ used for $P_{\gamma}$-shattering
$d:=\mathrm{P_{\gamma}}(A)$ many columns of $A$ must belong to the interval
$[\gamma,1-\gamma]$. Any threshold $t_{i}$ can be rounded to the closest
multiple of $\gamma$. Denote the latter by $\hat{t}_{i}$. The inequality (3.3)
becomes now evident from the following observations. First, by using the
thresholds $\hat{t}_{i}$ instead of $t_{i}$, the width of shattering may drop
from $\gamma$ to $\gamma/2$ (but not beyond). Second,
$\hat{t}_{1},\ldots,\hat{t}_{d}$ can take on at most

$r:=\left\lceil\frac{1-2\gamma}{\gamma}\right\rceil+1=\left\lceil\frac{1}{\gamma}\right\rceil-1\
$

different values. By the pidgeon-hole principle, there is some
$t\in\\{\hat{t}_{1},\ldots,\hat{t}_{d}\\}$ that can be used for
$V_{\gamma/2}$-shattering $d/r$ many points. ∎

###  3.2 Bounding dual dimension in terms of its primal

A well-known result due to Assouad [2] already mentioned in Section 1, which
we will refer to as _Assouad’s bound_ , states that one can upper bound the
dual VC-dimension in terms of the (primal) VC-dimension.

######  Theorem 3.5 ([2]).

For every matrix $A:X\times Y\rightarrow\\{0,1\\}$, we have

$\mathrm{VC}^{*}(A)\leq 2^{\mathrm{VC}(A)+1}-1.$ (3.4)

Note that, under the assumption that $\mathrm{VC}^{*}(A)$ is a power of two,
this means

$\mathrm{VC}^{*}(A)\leq 2^{\mathrm{VC}(A)}.$ (3.5)

The bound in (3.5) is known to be tight for every value of $\text{VC}(A)$,
see, e.g., [7].

In Appendix A we show that the Assouad’s bound also holds for
$\mathrm{Vdim}(A)$ and $V_{\gamma}(A)$, based on the notion of _uniform
$\Psi$-dimension_ as defined in [1]. These observations are summarized in the
following result.

######  Corollary 3.6 (Folklore).

For every matrix $A:X\times Y\rightarrow[0,1]$, we have

$\mathrm{Vdim}^{*}(A)\leq 2^{\mathrm{Vdim}(A)+1}-1\ \mbox{ and }\
V_{\gamma}^{*}(A)\leq 2^{\mathrm{V_{\gamma}}(A)+1}-1.$ (3.6)

If $\mathrm{Vdim}^{*}(A)$, respectively $V_{\gamma}^{*}(A)$, is a power of
two, this means

$\mathrm{Vdim}^{*}(A)\leq 2^{\mathrm{Vdim}(A)}\ \mbox{ and }\
V_{\gamma}^{*}(A)\leq 2^{\mathrm{V_{\gamma}}(A)}.$ (3.7)

Combining Theorem 3.2 (applied to $A^{\top}$) with Corollary 3.6, we directly
obtain the following result:

######  Theorem 3.7 (Folklore).

For every matrix $A:X\times Y\rightarrow[k]_{0}$, the following holds:

  1. 1.

$\mathrm{Pdim}^{*}(A)\leq k\cdot\left(2^{\mathrm{Vdim}(A)+1}-1\right)\leq
k\cdot\left(2^{\mathrm{Pdim}(A)+1}-1\right)$.

  2. 2.

If $\mathrm{Vdim}^{*}(A)$ is a power of two, then $\mathrm{Pdim}^{*}(A)\leq
k\cdot 2^{\mathrm{Vdim}(A)}\leq k\cdot 2^{\mathrm{Pdim}(A)}$.

Similarly, combining Theorem 3.4 with Corollary 3.6, we directly obtain the
following result.

######  Corollary 3.8 (Folklore).

For every matrix $A:X\times Y\rightarrow[0,1]$, the following holds:

$P_{\gamma}^{*}(A)\leq\left(\left\lceil\frac{1}{\gamma}\right\rceil-1\right)\cdot\left(2^{\mathrm{V_{\gamma/2}}(A)+1}-1\right)\leq\left(\left\lceil\frac{1}{\gamma}\right\rceil-1\right)\cdot\left(2^{\mathrm{Pdim}(A)+1}-1\right).$

##  4 Our results

In this section we describe our new contributions, that complement those
mentioned in Section 3. We first discuss results related to the pseudo-
dimension. We start with a result showing that the upper bound on
$\mathrm{Pdim}^{*}(A)$ in Theorem 3.7 can be improved by a factor $2$
(roughly) for matrices $A$ with $\mathrm{Vdim}(A)=1$.

######  Theorem 4.1.

Let $A:X\times Y\rightarrow[k]_{0}$ with $k\geq 1$ be a matrix with
$\mathrm{Vdim}(A)=1$. Then $\mathrm{Pdim}^{*}(A)\leq k+2$.

The next result implies that the upper bound on $\mathrm{Pdim}^{*}(A)$ in the
second statement of Theorem 3.7 is tight for matrices with
$\mathrm{Vdim}(A)\geq 2$, as well as the upper bound on $\mathrm{Pdim}^{*}(A)$
in Theorem 4.1 whenever $\mathrm{Vdim}(A)\geq 1$.

######  Theorem 4.2.

The following two lower bounds hold:

  1. 1.

For every $d\geq 2$ and every $k\geq 1$, there exists a matrix $A:X\times
Y\rightarrow[k]_{0}$ such that

$\mathrm{Pdim}(A)=d\ ,\ \mathrm{Vdim}^{*}(A)=2^{d}\ \mbox{ and }\
\mathrm{Pdim}^{*}(A)=k\cdot 2^{d}.$

  2. 2.

For every $k\geq 1$, there exists a matrix $A:X\times Y\rightarrow[k]_{0}$
such that $\mathrm{Vdim}(A)=\mathrm{Pdim}(A)=1$ and
$\mathrm{Pdim}^{*}(A)=k+2$.

In combination with the a technical tool defined in Section 5.2, we also
obtain the following corollary. It stands in stark contrast to Assouad’s bound
for the VC-dimension.

######  Corollary 4.3.

There exist a matrix $A:X\times Y\rightarrow[0,1]$, such that
$\mathrm{Pdim}(A)=1$ and $\mathrm{Pdim}^{*}(A)=\infty$.

We next move to our results for the fat-shattering dimensions. The first
result here implies that upper bound on $\mathrm{P_{\gamma}}(A)$ from Theorem
3.4 is tight up to a small constant factor:

######  Theorem 4.4.

For every $d\geq 1$, there exists a matrix $A:X\times Y\rightarrow[0,1]$ such
that $\mathrm{Pdim}(A)=d$ and, for all $k\geq 1$,

$\mathrm{P_{1/(2k)}}(A)\geq k\cdot d\enspace.$

Finally, our last results state that the bound on $P_{\gamma}^{*}(A)$ from
Corollary 3.8 is tight up to a small constant factor.

######  Theorem 4.5.

The following two lower bounds hold:

  1. 1.

For every $d\geq 2$, there exists a matrix $A:X\times Y\rightarrow[0,1]$ such
that $\mathrm{Pdim}(A)=d$ and, for all $k\geq 1$,

$P_{1/(2k)}^{*}(A)=k\cdot 2^{d}\enspace.$

  2. 2.

There exists a matrix $A:X\times Y\rightarrow[0,1]$ such that
$\mathrm{Pdim}(A)=1$ and, for all $k\geq 2$,

$P_{1/(2k)}^{*}(A)=k+2\enspace.$

##  5 Proofs

Section 5.1 is devoted to the proof of Theorem 4.1. In Section 5.2, we make
some considerations which will allow for an easier presentation of our lower
bound constructions, that are given in Sections 5.3 and 5.4.

###  5.1 Proof of Theorem 4.1

For $k=1$, the assertion of the theorem collapses to the claim that
$\mathrm{VC}^{*}(A)\leq 3$ for every Boolean matrix $A$ with
$\mathrm{Vdim}(A)=1$. This is an immediate consequence of (3.4). Suppose now
that $k\geq 2$. It suffices to show that $\mathrm{Pdim}^{*}(A)\geq k+3$
implies that $\mathrm{Vdim}(A)\geq 2$ (i.e., we give a proof by
contradiction). Pick a witness $(I,J,\mathbf{t})$ for
$\mathrm{Pdim}^{*}(A)\geq k+3$. More concretely:

  * •

$I=\\{x_{1},\ldots,x_{k+3}\\}$, $J\subseteq Y$ with $|J|=2^{k+3}$ and
$\mathbf{t}:I\rightarrow[k]$, say $\mathbf{t}(x_{i})=t_{i}$.

  * •

The matrix obtained by thresholding the rows of $A_{I,J}$ at $\mathbf{t}$
equals $B_{k+3}^{\top}$.

We may assume that, after renumbering the rows appropriately, one has
$t_{1}\leq\ldots\leq t_{k+3}$. We decompose the rows of $A_{I,J}$ into maximal
blocks such that the same threshold is assigned to every row from the same
block. Since any threshold $t_{i}$ is taken from $[k]$, the total number
$k^{\prime}$ of blocks is bounded by $k$. A block that is different from the
first and from the last block is said to be an _inner block_. We proceed by
case analysis:

Case 1:

One of the blocks contains 4 rows.
Then $\mathrm{Vdim}^{*}(A)\geq 4$ is immediate. Thus
$\mathrm{Vdim}(A)\geq\lfloor\log\mathrm{Vdim}^{*}(A)\rfloor\geq 2$.

Case 2:

The first or the last block contains 3 rows.
For reasons of symmetry, we may assume that the first block contains 3 rows.
Consider the following $(4\times 2)$-submatrix of $B_{k+3}^{\top}$:

$\begin{array}[]{cc}0&0\\\ 0&1\\\ 1&0\\\ \hline\cr 1&1\end{array}$

The first three rows are taken from the first block and the last row is taken
from the last block. The separation line between the third and the last row is
only intended to illustrate the transition from one block to another. Remember
that the rows of the first block of $A_{I,J}$ are thresholded at $t_{1}$ while
the rows of the last block are thresholded at $t_{k^{\prime}}>t_{1}$. Hence,
if we threshold _all rows_ (or _all columns_) of $A_{I,J}$ at $t_{1}$, then
the above submatrix of $B_{k+3}^{\top}$ will remain unchanged. We may conclude
from this discussion that $\mathrm{Vdim}(A)\geq 2$.

Case 3:

One of the inner blocks contains 2 rows, say block $b$.
The argument is similar to that given in Case 2. The relevant submatrix of
$B_{k+3}^{\top}$ (with one row of the first block, two rows of block $b$, one
row of the last block and two separation lines inbetween) now looks as
follows:

$\begin{array}[]{cc}0&0\\\ \hline\cr 0&1\\\ 1&0\\\ \hline\cr 1&1\end{array}$

Since $t_{1}<t_{b}<t_{k^{\prime}}$, thresholding all rows (or all columns) of
$A_{I,J}$ at $t_{b}$ will leave the above submatrix of $B_{k+3}^{\top}$
unchanged. We may conclude that $\mathrm{Vdim}(A)\geq 2$.

Since $A_{I,J}$ has $k+3$ rows (with $k\geq 2$), it is easy to argue that one
of the three above cases must occur. Suppose first that $k=2$. Then there at
most $2$ blocks and $5$ rows. It follows that the first or the last block
contains at least $3$ rows. Suppose now that $k\geq 3$. If the first and the
last block contain at most two rows, respectively, then at least $k-1$ rows
are left for the $k^{\prime}-2\leq k-2$ inner blocks. By the pidgeon-hole
principle, there must be an inner block with two rows. This completes the
proof of Theorem 4.1.

###  5.2 Preliminaries for lower bound constructions

Consider again the Boolean matrix $B_{d}$ with $d$ columns and $2^{d}$ rows
that had been defined in Section 2. It is evident that $B_{d}$ satisfies the
following conditions:

  1. i)

Distinctness Condition: The rows of $B_{d}$ are pairwise distinct.

  2. ii)

General Balance Condition: For any $k\in[d]$, any choice of $k$ distinct
columns of $B_{d}$ and any pattern $\mathbf{b}\in\\{0,1\\}^{k}$, there are
exactly $2^{d-k}$ rows of $B_{d}$ which realize the pattern $\mathbf{b}$
within the chosen columns.

The general balance condition implies the following:

  1. iii)

1st Balance Condition: Each column of $B_{d}$ has as many zeros as ones.

  2. iv)

2nd Balance Condition: For any two distinct columns of $B_{d}$, any pattern
from $\\{0,1\\}^{2}$ is realized within these columns by the same number of
rows.

######  Remark 5.1 (Proof templates).

Consider a matrix $A:X\times Y\rightarrow[k]_{0}$. The following template for
proving assertions like $\mathrm{Pdim}(A)\leq d$ will prove itself quite
useful.

  * •

Assume for contradiction that $\mathrm{Pdim}(A)\geq d+1$.

  * •

Pick a witness $(I,J,\mathbf{t})$ for this inequality.

  * •

Exploit the fact that the matrix $B$ obtained by thresholding the columns of
$A_{I,J}$ at $\mathbf{t}$ must be equal to $B_{d+1}$.

  * •

Prove that $B$ violates one of the conditions that $B_{d+1}$ must satisfy.

Sometimes the following (slightly simpler) template can be used instead:

  * •

Take a fixed but arbitrary function $\mathbf{t}:Y\rightarrow[k]$.

  * •

Let $B$ be the matrix obtained by thresholding the columns of $A$ at
$\mathbf{t}$.

  * •

Show that no more than $d$ columns of $B$ have at least $2^{d}$ zeros and at
least $2^{d}$ ones.

This also shows that $\mathrm{Pdim}(A)\leq d$ because no submatrix of $B$ with
$d+1$ columns and $2^{d+1}$ rows has a chance to satisfy the first balance
condition.

We next introduce matrices that, though not being Boolean, are close relatives
of the matrix $B_{d}$.

######  Definition 5.2.

Let $k$ and $d_{1},\ldots,d_{k}$ be positive integers and let
$D=d_{1}+\ldots+d_{k}$ denote their sum. The _$B_{D}$ -based matrix with $k$
column blocks of sizes $d_{1},\ldots,d_{k}$_ is the matrix $A:X\times
Y\rightarrow[k]_{0}$, where $X=[2^{D}]$ and $Y=[D]$, that results from the
following procedure:

  1. 1.

Decompose the $D$ columns of $B_{D}$ into $k$ blocks of sizes
$d_{1},\ldots,d_{k}$. The blocks are consecutively numbered from $1$ to $k$.

  2. 2.

Obtain $A$ from $B_{D}$ by replacing any $1$-entry (resp. $0$-entry) in a
column belonging to block $b\in[k]$ by $b$ (resp. by $b-1$).

The _$B_{D}^{\top}$ -based matrix with $k$ row blocks of sizes
$d_{1},\ldots,d_{k}$_ is defined analogously.

Note that the matrix $A$ resulting from the above procedure has the property
that, for any two columns $y_{1}$ in block $b_{1}$ and $y_{2}$ in block
$b_{2}>b_{1}$ and any row $x$, we have $A(x,y_{1})\leq A(x,y_{2})$. We will
refer to this property as _block monotonicity_.

At this point we also bring into play the matrix $\dot{A}$, which is defined
as the matrix $A$ augmented with a row of zeros. Formally, we assume that
$0\notin X$ and define $\dot{A}:(X\cup\\{0\\})\times Y\rightarrow Z$ as the
extension of $A$ which satisfies $\dot{A}(0,y)=0$ for all $y\in Y$. The
(technical) use of $\dot{A}$ will become clear in Section 5.4 (in particular,
this is explained after Definition 5.7), but it is already included in the
statements that follow.

######  Lemma 5.3.

Let $D=d_{1}+\ldots+d_{k}$ and let $A$ be the $B_{D}$-based matrix with $k$
column blocks of sizes $d_{1},\ldots,d_{k}$. Then
$\mathrm{Vdim}(A)=\mathrm{Vdim}(\dot{A})=\max_{j\in[k]}d_{j}$ and
$\mathrm{Pdim}(A)=\sum_{j=1}^{k}d_{j}$.

###### Proof.

We first show that the pseudo-dimension of $A$ equals $D$. Let
$\mathbf{t}:[D]\rightarrow[k]$ be the mapping that assigns to every column in
block $j\in[k]$ the threshold $j$. Then the matrix obtained by thresholding
the columns of $A$ at $\mathbf{t}$ equals $B_{D}$. It follows that
$\mathrm{Pdim}(A)\geq\mathrm{VC}(B_{D})=D$. Of course $\mathrm{Pdim}(A)$
cannot exceed $D$ so that $\mathrm{Pdim}(A)=D$.

Next, set $d_{max}=\max_{j\in[k]}d_{j}$. Pick some index $j_{max}\in[k]$ such
that $d_{j_{max}}=d_{max}$. We still have to show that
$\mathrm{Vdim}(A)=\mathrm{Vdim}(\dot{A})=d_{max}$. Thresholding the columns of
$A$ at the uniform threshold $j_{max}$, we obtain a matrix $B$ that equals
$B_{D}$ within block $j_{max}$. This shows that $\mathrm{Vdim}(A)\geq
d_{max}$. The inequality $\mathrm{Vdim}(\dot{A})\leq d_{max}$ can be seen as
follows. Pick a fixed but arbitrary $J\subseteq[D]$ of size $1+d_{max}$ and a
fixed but arbitrary uniform threshold $t\in[k]$. Let $B$ be the matrix
obtained by thresholding the columns of $\dot{A}$ at $t$. The set $J$ must
contain two columns belonging to two different blocks, say column $y_{1}$ in
block $b_{1}$ and column $y_{2}$ in block $b_{2}>b_{1}$. By the block-
monotonicity of $A$ (which implies block-monotonicity for $\dot{A}$ as well),
no row of $B$ can assign label $1$ to $y_{1}$ and label $0$ to $y_{2}$. Since
$J$ and $t$ were arbitrary choices, it follows that no set of size $1+d_{max}$
can be $V$-shattered by $\dot{A}$. ∎

Setting $d_{1}=\ldots=d_{k}=d$ in Lemma 5.3, we obtain the following result
(which is almost the same as Theorem 3.2):

######  Corollary 5.4.

For every $d\geq 1$ and every $k\geq 1$, there exists a matrix $A:X\times
Y\rightarrow[k]_{0}$ such that $\mathrm{Vdim}(A)=\mathrm{Vdim}(\dot{A})=d$ and
$\mathrm{Pdim}(A)=k\cdot d$.

###  5.3 Proof of Theorem 4.2

Theorem 4.2 is a direct consequence of the following two results:

######  Lemma 5.5.

Let $d\geq 2$ and $k\geq 1$ be given. For $D=k\cdot 2^{d}$, let $A$ be the
$B_{D}^{\top}$-based matrix with $k$ row blocks of size $2^{d}$, respectively.
Then

$\mathrm{Pdim}(A)=\mathrm{Pdim}(\dot{A})=d\ ,\ \mathrm{Vdim}^{*}(A)=2^{d}\
\mbox{ and }\ \mathrm{Pdim}^{*}(A)=k\cdot 2^{d}\enspace.$

###### Proof.

The identities $\mathrm{Vdim}^{*}(A)=2^{d}$ and $\mathrm{Pdim}^{*}(A)=k\cdot
2^{d}$ are immediate from Lemma 5.3. Hence it suffices to verify the identity
$\mathrm{Pdim}(A)=\mathrm{Pdim}(\dot{A})=d$. We can infer from
$\mathrm{Vdim}^{*}(A)=2^{d}$ that
$\mathrm{Pdim}(\dot{A})\geq\mathrm{Pdim}(A)\geq\mathrm{Vdim}(A)\geq d$. Hence
the proof can be accomplished by showing that $\mathrm{Pdim}(\dot{A})\leq d$.
For sake of brevity, set

$s=2^{d}\ \mbox{ and }\ \bar{d}=1+d\enspace.$

Assume for contradiction that $\mathrm{Pdim}(\dot{A})\geq\bar{d}$ and fix some
witness $(I,J,\mathbf{t})$ for this inequality, i.e.,

  1. 1.

$I\subseteq[D]_{0}$, $|I|=2^{\bar{d}}$, $J\subseteq[2^{D}]$, $|J|=\bar{d}$ and
$\mathbf{t}:J\rightarrow[k]$ assigns a threshold to each column of
$A_{I,J}$.555Recall from the definition of $\dot{A}$ that this matrix is
obtained from $A$ by adding an all-zeros row which is indexed by $0$.

  2. 2.

The matrix $B$ obtained by thresholding the columns of $A_{I,J}$ at
$\mathbf{t}$ equals $B_{\bar{d}}$.

Before we proceed with the proof, we fix some notation. For $b=1,\ldots,k$,
let $I_{b}$ denote the set of row indices in $I$ that belong to block $b$ of
$A$. Set $I_{0}=I\cap\\{0\\}$ and note that

$\sum_{b=0}^{k}|I_{b}|=|I|=2^{\overline{d}}=2s\ \mbox{ (twice the block
size)}$

while, for every $b\in[k]$, we clearly have $0\leq|I_{b}|\leq s$. Let
$b_{0},b^{\prime}_{0}$ (resp. $b_{1},b^{\prime}_{1}$) denote the smallest and
second-smallest (resp. largest and second-largest) $b\in[k]$ such that
$|I_{b}|\neq 0$.
An obvious question is whether $0\in I$, that is, whether the extra all-zeros
row is among the rows of $B$. We claim that this is not the case. Assume for
contradiction that $0\in I$. We proceed by case analysis:

Case 1:

$1\leq|I_{b_{0}}|\leq s-1$.
Pick an arbitrary but fixed column $j\in J$ of $B$. In order to satisfy the
first balance condition, the threshold $t_{j}$ must be large enough so that in
block $b_{0}$ of column $j$ only 0-entries are found.666A single 1-entry in
this block would imply that we have only 1-entries in all subsequent blocks.
It follows that any row of $B$ belonging to block $b_{0}$ has 0-entries only
and therefore coincides with the extra all-zeros row. This is in contradiction
with the distinctness condition.

Case 2:

$|I_{b_{0}}|=s$.
Pick an arbitrary but fixed column $j\in J$ of $B$. In order to satisfy the
first balance condition, the threshold $t_{j}$ must be large enough so that in
block $b_{0}$ of column $j$ at least $s-1$ 0-entries are found. Pick another
column $j^{\prime}\neq j$ in $B$ (also with at least $s-1$ 0-entries in block
$b_{0}$). Then the pattern $00$ occurs in columns $j$ and $j^{\prime}$ of $B$
at least $s-1$ times (one time in row $0$ and at least $s-2$ times in block
$b_{0}$). But then $B$ must have at least $4(s-1)$ rows in order to satisfy
the second balance condition. Hence $4(s-1)\leq 2s$ (because $B$ has $2s$
rows). It follows that $s\leq 2$, which is in contradiction with our
assumptions that $d\geq 2$ and $s=2^{d}\geq 4$.

In any case, we arrived at a contradiction, which proves the above claim that
$0\notin I$. In order to accomplish the proof, we still have to derive a final
contradiction. We proceed by case distinction again.

Case A:

$|I_{b_{0}}|\geq 2$.
In order to satisfy the first balance condition, the threshold $t_{j}$ of any
column $j\in J$ must be large enough so that in block $b_{0}$ of this column
only 0-entries are found. Thus all rows of $B$ belonging to block $b_{0}$
realize the all-zeros pattern, which is in contradiction with the distinctness
condition.

Case B:

$|I_{b_{0}}|=1$ and $|I_{b^{\prime}_{0}}|\leq s-1$.
The argument is similar. Now the single row of $B$ belonging to block $b_{0}$
and all rows of $B$ belonging to block $b^{\prime}_{0}$ realize the all-zeros
pattern.

Case C:

$|I_{b_{1}}|\geq 2$ or $(|I_{b_{1}}|=1$ and $|I_{b^{\prime}_{1}}|\leq s-1$).
Then, for reasons of symmetry, the last two rows of $B$ both realize the all-
ones pattern.

Case D:

$|I_{b_{0}}|=|I_{b_{1}}|=1$ and $|I_{b^{\prime}_{0}}|=|I_{b^{\prime}_{1}}|=s$.
Since $|I|=2s$, this case can occur only if $b^{\prime}_{0}=b^{\prime}_{1}$.
But then $2s=|I|=|I_{b_{0}}|+|I_{b^{\prime}_{0}}|+|I_{b_{1}}|=s+2$ so that
$s=2$. This contradicts to our assumption $d\geq 2$ and $s=2^{d}\geq 4$.

In any case, we arrived at a contradiction. ∎

######  Lemma 5.6.

Let $k\geq 2$ and let$A$ be the $B_{k+2}^{\top}$-based matrix with $k$ row
blocks of sizes

$d_{j}=\left\\{\begin{array}[]{ll}2&\text{ for }j=1,k\\\ 1&\text{ for
}j=2,\dots,k-1\end{array}\right..$

Then $\mathrm{Pdim}(A)=\mathrm{Pdim}(\dot{A})=1$ and
$\mathrm{Pdim}^{*}(A)=k+2$.

###### Proof.

The identity $\mathrm{Pdim}^{*}(A)=k+2$ is immediate from Lemma 5.3. Clearly
$\mathrm{Pdim}(\dot{A})\geq\mathrm{Pdim}(A)\geq 1$. Hence it suffices to show
that $\mathrm{Pdim}(\dot{A})\leq 1$. The rows of $\dot{A}$ have indices
$0,1,\ldots,k+2$ and index $0$ is reserved for the all-zeros row. Assume for
contradiction that $\mathrm{Pdim}(\dot{A})\geq 2$ and pick a witness $(I,J,t)$
for this inequality so that the following holds:

  * •

$J=\\{j_{1},j_{2}\\}\subset[2^{k+2}]$, $I\subseteq[k+2]_{0}$ with $|I|=4$ and
$\mathbf{t}:J\rightarrow[k]$, say $\mathbf{t}(j_{1})=t_{1}$ and
$\mathbf{t}(j_{2})=t_{2}$.

  * •

The matrix $B$ obtained by thresholding the columns of $\dot{A}_{I,J}$ at
$\mathbf{t}$ equals $B_{2}$ (with rows indexed by $I$ and columns indexed by
$J$).

Consequently $B$ satisfies the distinctness condition and the balance
conditions. Consider the smallest index $i_{1}$ and the second-smallest index
$i_{2}$ in $I$. Note that, since $|I|=4$ and the last block of $B$ is of size
$2$, neither $i_{1}$ nor $i_{2}$ belongs to the last block, i.e., either
$i_{1},i_{2}\in\\{0,1,2\\}$ or $i_{2}$ belongs to one of the inner blocks
consisting of a single row only. In order to establish the first balance
condition for the matrix $B$, the thresholds $t_{1}$ and $t_{2}$ must be large
enough so that only zeros are found in the first two components (indexed by
$i_{1}$ and $i_{2}$) of the columns $j_{1}$ and $j_{2}$. Thus the first two
rows of $B$ both realize the all-zeros pattern, which is in contradiction with
the distinctness condition. ∎

Lemma 5.6 does not cover the case $k=1$ in the second assertion of Theorem
4.2. But this case is easy to handle: setting $A=B_{3}^{\top}$, we obtain
$\mathrm{Pdim}^{*}(A)=\mathrm{VC}^{*}(A)=3$ and
$\mathrm{Pdim}(A)=\mathrm{VC}(A)=1$.

###  5.4 Proofs of Theorems 4.4 and 4.5

Matrices $A$ with the properties as prescribed by Theorems 4.4 and 4.5 are
easy to construct by means of a suitable operation that merges matrices of a
given matrix family into a single matrix.

######  Definition 5.7 (Merge-operation).

Let $(A_{k})_{k\geq 1}$ with $A_{k}:X_{k}\times Y_{k}\rightarrow[k]_{0}$ be a
given family of matrices. Let $X$ (resp. $Y$) denote the disjoint union of the
sets $X_{k}$ (resp. $Y_{k}$) with $k\geq 1$. Assume that $X\cap Y=\emptyset$.
For every $x\in X$, let $k(x)$ denote the unique $k$ such that $x\in X_{k}$.
The notation $k(y)$ is understood analogously. The matrix $A:X\times
Y\rightarrow[0,1]$ given by

$A(x,y)=\left\\{\begin{array}[]{ll}\frac{A_{k(x)}(x,y)}{k(x)}&\mbox{if
$k(y)=k(x)$}\\\ 0&\mbox{otherwise}\end{array}\right.\enspace,$

is called the _merge of the family $(A_{k})_{k\geq 1}$_.

The merge-operation reveals why we introduce the matrix $\dot{A}$: The pseudo-
dimension (or any other combinatorial dimension for that matter) of the matrix
$A$ restricted to the columns $Y_{k}$ is nothing more than the pseudo-
dimension of the functions in $A_{k}$ augmented with an infinite number of
functions that are zero everywhere. The pseudo-dimension of this function
class clearly equals the pseudo-dimension of the matrix $\dot{A}_{k}$. The
merge-operation has the following properties:

######  Lemma 5.8.

Let $A$ be the merge of the family $(A_{k})_{k\geq 1}$. Then the following
holds:

  1. 1.

$\mathrm{P_{1/(2k)}}(A)\geq\mathrm{Pdim}(A_{k})$.

  2. 2.

Let $d_{0}\in\mathbb{N}$. If $\sup_{k}\mathrm{Pdim}(\dot{A}_{k})\leq d_{0}$,
then $\mathrm{Pdim}(A)\leq d_{0}$.

  3. 3.

$\mathrm{V_{1/(2k)}}(A)\geq\mathrm{Vdim}(A_{k})$.

  4. 4.

Let $d_{0}\in\mathbb{N}$. If $\sup_{k}\mathrm{Vdim}(\dot{A}_{k})\leq d_{0}$,
then $\mathrm{Vdim}(A)\leq d_{0}$.

###### Proof.

We only prove the first two assertions of the lemma; the other two assertions
are quite similar.

Note that, for $k=k(x)=k(y)$, $A$ coincides with $A_{k}$ except for scaling
down the values $0,1,\ldots,k$ by factor $k$. Since $A_{k}$ takes integer
values, each set that can be $P$-shattered by $A_{k}$ can actually be
$P_{1/2}$-shattered. After down-scaling, the width of shattering becomes
$1/(2k)$. From these observations, the first assertion of the lemma easily
follows.

We proceed with the proof of the second assertion. Set $d:=\mathrm{Pdim}(A)$.
Fix some witness $(I,J,\mathbf{t})$ so that the following holds:

  1. 1.

$I\subset X$, $|I|=2^{d}$, $J\subset Y$, $|J|=d$ and
$\mathbf{t}:J\rightarrow\mathbbm{N}$ assigns a threshold
$t_{y}:=\mathbf{t}(y)$ to every $y\in J$.

  2. 2.

The matrix $B$ obtained by thresholding the columns of $A_{I,J}$ at
$\mathbf{t}$ equals $B_{d}$ (with rows indexed by $I$ and columns indexed by
$J$).

It follows that $B$ satisfies the distinctness condition and the balance
conditions.

Claim 1: For every $y\in J$, we have $t_{y}>0$.

###### Proof.

$t_{y}\leq 0$ would imply that column $y$ of $B$ has no 0-entry, which is in
contradiction with the first balance condition. ∎

Claim 2: The mapping $y\mapsto k(y)$ assigns the same value to all $y\in J$.

###### Proof.

Assume to the contrary that there exist $y_{1},y_{2}\in J$ such that
$k(y_{1})\neq k(y_{2})$. Then, for every row $x$ of $B$, at least one of the
entries $B[x,y_{1}]$ and $B[x,y_{2}]$ equals $0$ (because $k(x)$ cannot be
equal to both, $k(y_{1})$ and $k(y_{2})$). By the first balance condition, any
column in $B$ has as many 0- as 1-entries. Since this is particularly true for
the columns $y_{1}$ and $y_{2}$, it follows that, for every row $x$ of $B$,
exactly one of the entries $B[x,y_{1}]$ and $B[x,y_{2}]$ equals $0$. Thus
column $y_{2}$ of $B$ is the entry-wise logical negation of the column
$y_{1}$. This, however, is in contradiction with the second balance condition.
∎

Claim 3: Let $k_{1}$ denote the common $k$-value of $y_{1},\ldots,y_{d}$. Then
any row $x$ in $B$ with $k(x)\neq k_{1}$ has 0-entries only.

###### Proof.

This is straighforward. ∎

We conclude from Claims 2 and 3 that
$\mathrm{Pdim}(A)=d\leq\mathrm{Pdim}(\dot{A}_{k_{1}})$ and, by assumption, the
latter quantity is at most $d_{0}$, which concludes the proof. ∎

Theorem 4.4 is now a direct consequence of Lemma 5.8 in combination with
Corollary 5.4, while Theorem 4.5 is a direct consequence of Lemma 5.8 in
combination with Lemmas 5.5 and 5.6. In order to prove Corollary 4.3, note
that Lemma 5.6 tells us that for every $k$ there exists a matrix $A_{k}$ such
that $\mathrm{Pdim}(\dot{A}_{k})=1$ and
$\mathrm{Pdim}^{*}(\dot{A}_{k})\geq\mathrm{Pdim}^{*}(A_{k})=k+2$. We may then
apply Lemma 5.8.

#### Acknowledgements.

The first author thanks Tim Roughgarden for discussions that (indirectly) lead
to the questions studied in this work.

## References

  * [1] Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler.  Scale-sensitive dimensions, uniform convergence, and learnability.  J. ACM, 44(4):615–631, July 1997.
  * [2] Patrick Assouad.  Densité et dimension.  Annales de l’Institut Fourier, 33(3):233–282, 1983.
  * [3] Shai Ben-David, Nicolo Cesabianchi, David Haussler, and Philip M Long.  Characterizations of learnability for classes of [n]-valued functions.  Journal of Computer and System Sciences, 50(1):74–86, 1995.
  * [4] Steve Hanneke, Aryeh Kontorovich, and Menachem Sadigurschi.  Sample compression for real-valued learners.  In Algorithmic Learning Theory, pages 466–488. PMLR, 2019.
  * [5] David Haussler.  Decision theoretic generalizations of the pac model for neural net and other learning applications.  Information and computation, 100(1):78–150, 1992.
  * [6] Michael J Kearns and Robert E Schapire.  Efficient distribution-free learning of probabilistic concepts.  Journal of Computer and System Sciences, 48(3):464–497, 1994.
  * [7] Jiří Matoušek.  Lectures on discrete geometry, volume 108.  Springer, 2002.
  * [8] Shay Moran and Amir Yehudayoff.  Sample compression schemes for VC classes.  J. ACM, 63(3):21:1–21:10, 2016.
  * [9] David Pollard.  Empirical processes: theory and applications.  In NSF-CBMS regional conference series in probability and statistics, pages i–86. JSTOR, 1990.
  * [10] Vladimir Naumovich Vapnik.  Inductive principles of the search for empirical dependences (methods based on weak convergence of probability measures).  In Proceedings of the Second Annual Workshop on Computational Learning Theory, pages 3–21, San Mateo, CA, August 1989. Morgan Kaufmann.
  * [11] Vladimir Naumovich Vapnik and Aleksei Yakovlevich Chervonenkis.  On uniform convergence of the frequencies of events to their probabilities.  Theory of Probability and its Applications, 16(2):264–281, 1971\.

##  Appendix A On the derivation of Assouad’s bound for uniform dimensions

We say that $J\subseteq Y$ is _VC-shattered_ by $A:X\times
Y\rightarrow\\{0,1,*\\}$ if, for every function $b:J\rightarrow\\{0,1\\}$,
there exists an $x\in X$ such that, for every $y\in J$, we have $B(x,y)=b(y)$.
We first note that (3.4) is also valid for every matrix of the form $A:X\times
Y\rightarrow\\{0,1,*\\}$: the central observation in the proof is that $B_{d}$
contains $B^{\top}_{\lfloor\log d\rfloor}$ as a submatrix. This implies that
$\mathrm{VC}(A)\geq\lfloor\log\mathrm{VC}^{*}(A)\rfloor$, which is equivalent
to (3.4).

Consider now a matrix of the general form $A:X\times Y\rightarrow Z$ with
$Z\subseteq\mathbbm{R}$. Making use of the concept of uniform
$\Psi$-dimensions from [3], the result of Assouad can be extended to several
other combinatorial dimensions. Let $\Psi$ denote a family of substitutions of
the form $\psi:\mathbbm{R}\rightarrow\\{0,1,*\\}$. Denote by $\psi(A)$ the
matrix obtained from $A$ by performing the substitution $\psi$ entry-wise. The
_uniform $\Psi$-dimension_ of $A$ is then defined as

$\mathrm{\Phi}_{U}(A)=\sup_{\psi\in\Psi}\mathrm{VC}(\psi(A))\enspace.$

Let $\Psi_{Y}$ denote the set of all collections $\bar{\psi}=(\psi_{y})_{y\in
Y}$ with $\psi_{y}\in\Psi$. Denote by $\bar{\psi}(A)$ the matrix obtained from
$A$ by replacing each entry $A(x,y)$ with $\psi_{y}(A(x,y))$. The _(non-
uniform) $\Psi$-dimension_ of $A$ is defined as

$\mathrm{\Phi}(A)=\sup_{\bar{\psi}\in\Psi_{Y}}\mathrm{VC}(\bar{\psi}(A))\enspace.$

As usual, we get the corresponding dual dimensions by setting
$\mathrm{\Phi}^{*}(A)=\mathrm{\Phi}(A^{\top})$ and
$\mathrm{\Phi}^{*}_{U}(A)=\mathrm{\Phi}_{U}(A^{\top})$. Note that
$\psi(A^{\top})=\psi(A)^{\top}$ while $\bar{\psi}(A^{\top})$ is not generally
equal to $\bar{\psi}(A)^{\top}$.

As noted in [3], several popular combinatorial dimensions can be viewed as
(uniform or non-uniform) $\psi$-dimension. Here we are particularly interested
in the $P$-, $P_{\gamma}$, $V$-and $V_{\gamma}$-dimension:

######  Remark A.1.

We next explain how to interpret known dimensions as special cases of the
$\Psi$-dimension.

  1. 1.

If $\Psi$ is the set of mappings $\psi_{t}$ of the form
$\psi_{t}(a)=\mbox{sgn}(a-t)$ for some $t\in\mathbbm{R}$, then
$\mathrm{\Phi}(A)=\mathrm{Pdim}(A)$ and
$\mathrm{\Phi}_{U}(A)=\mathrm{Vdim}(A)$ (see [3]).

  2. 2.

If $\Psi$ is the set of mappings $\psi_{t}$ of the form

$\psi_{t}(a)=\left\\{\begin{array}[]{ll}1&\mbox{if $a\geq t+\gamma$}\\\
0&\mbox{if $a<t-\gamma$}\\\ &\mbox{otherwise}\end{array}\right.$

for some $t\in\mathbbm{R}$ and $\gamma>0$, then
$\mathrm{\Phi}(A)=\mathrm{P_{\gamma}}(A)$ and
$\mathrm{\Phi}_{U}(A)=V_{\gamma}(A)$.

The following calculation, with $\psi$ ranging over all functions in $\Psi$,
shows that Theorem 3.5 can be extended to any uniform $\Psi$-dimension at the
place of the VC-dimension:

$\displaystyle\mathrm{\Phi}_{U}^{*}(A)$ $\displaystyle=$
$\displaystyle\mathrm{\Phi}_{U}(A^{\top})=\sup_{\psi}\mathrm{VC}(\psi(A^{\top}))=\sup_{\psi}\mathrm{VC}(\psi(A)^{\top})$
$\displaystyle=$
$\displaystyle\sup_{\psi}\mathrm{VC}^{*}(\psi(A))\leq\sup_{\psi}\left(2^{\mathrm{VC}(\psi(A))+1}-1\right)$
$\displaystyle=$ $\displaystyle
2^{\sup_{\psi}\mathrm{VC}(\psi(A))+1}-1=2^{\mathrm{\Phi}_{U}(A)+1}-1\enspace.$

We remark that a similar argument for the non-uniform $\Psi$-dimension fails
as it then no longer holds that $\bar{\psi}(A^{\top})=\bar{\psi}(A)^{\top}$
(which is the argument we use in the third equality above).