\documentclass[twoside,11pt]{article} \usepackage{jmlr2e,amsmath,amssymb,amscd,graphics,eucal} %\usepackage{jmlr2e,amsmath,amssymb,amscd,graphics,eucal,rotfloat} \jmlrheading{2}{2001}{$1$-$18$}{2/01}{10/01}{Shahar Mendelson} \ShortHeadings{On the Size of Convex Hulls of Small Sets} {Mendelson} \firstpageno{1} \newcommand{\Ef}{\E_\mu \Ell_f} \newcommand{\Pn}[1]{{\mathbb{P}}_{\mu_n}(\Ell_{#1})} \newcommand{\En}[1]{\E_\mu_n{#1}} \newcommand{\Emul}[1]{\E_\mu \Ell_{#1}} \newcommand{\iger}[1]{\lceil {#1} \rceil} \newcommand{\F}{\cal F \rm} \newcommand{\vol}{\mathop{\rm vol}\!} \newcommand{\adj}{\mathop{\rm adj}\,} \newcommand{\rank}{\mathop{\rm rank}} \newcommand{\TT}{\tilde T} \newcommand{\rond}{\mathbin{\scriptstyle\circ}} %\newcommand{\R}{{\rm I}\!{\rm R}} \newcommand{\R}{\mathbb{R}} \newcommand{\norm}[1]{\left\Vert #1\right\Vert} \newcommand{\abs}[1]{\left\vert #1\right\vert} \newcommand{\inr}[1]{\bigl< #1 \bigr>} \newcommand{\C}{{\bf C}} %\newcommand{\N}{{\rm I}\!{\rm N}} \newcommand{\N}{\mathbb{N}} %\newcommand{\E}{{\rm I}\!{\rm E}} \newcommand{\E}{\mathbb{E}} \newcommand{\T}{{\bf T}} \newcommand{\eps}{\varepsilon} \newcommand{\spec}{\mathop{\rm}} \newcommand{\ord}{\mathop{\rm ord}} \newcommand{\MM}{{\cal M}} \newcommand{\conv}{\mathop{\rm conv}} %\newcommand{\PP}{{\rm I}\!{\rm P}} \newcommand{\PP}{\mathbb{P}} \newcommand{\LL}{{\rm I}\!{\rm L}} \newcommand{\BB}{{\rm I}\!{\rm B}} \newcommand{\Eff}{F} \newcommand{\om}{\omega} \newcommand{\Ell}{\cal L} % SPECIFIC COMMANDS \newcommand{\normF}[1]{\left\Vert #1 \right\Vert_{\ell_\infty(F)}} \newcommand{\normpol}[1]{\norm{#1}_{(F/\mu_n)^o}} \newcommand{\sff}[1]{{\rm fat}_{#1}^{\frac{1}{2}}(F)} \newcommand{\ff}[1]{{\rm fat}_{#1}(F)} \newcommand{\base}{(n^{1/2}e_i)_{i \in I}} \newcommand{\packt}[1]{\log{D\bigl(#1,F,L_2(\mu_n)\bigr)}} \newcommand{\covert}[1]{\log{N\bigl(#1,F,L_2(\mu_n)\bigr)}} \newcommand{\scovert}[1]{\log^{\frac{1}{2}}{N\bigl(#1,F,L_2(\mu_n)\bigr)}} \newcommand{\pack}[1]{\log{D\bigl(#1,F,L_p(\mu_n)\bigr)}} \newcommand{\cover}[1]{\log{N\bigl(#1,F,L_p(\mu_n)\bigr)}} \newcommand{\scover}[1]{\log^{\frac{1}{2}}{N\bigl(#1,F,L_p(\mu_n)\bigr)}} \newcommand{\bi}{B\bigl(L_\infty(\Omega)\bigr)} \newcommand{\aconv}{{\rm absconv}} \newcommand{\Gauss}{\norm{\sum_{i=1}^n g_i\delta_{X_i}}_{\ell_\infty(F)}} \newcommand{\Rad}{\norm{\sum_{i=1}^n r_i\delta_{X_i}}_{\ell_\infty(F)}} \newtheorem{Theorem}{Theorem}[section] \newtheorem{Lemma}[Theorem]{Lemma} \newtheorem{Sublemma}{Sublemma} \newtheorem{Definition}[Theorem]{Definition} \newtheorem{Problem}[Theorem]{Problem} \newtheorem{Proposition}[Theorem]{Proposition} \newtheorem{Corollary}[Theorem]{Corollary} \newtheorem{Remark}[Theorem]{Remark} \newtheorem{Example}[Theorem]{Example} \newtheorem{Assumption}{Assumption}[section] \newtheorem{Question}[Theorem]{Question} \numberwithin{equation}{section} \font\titre=cmbx12 \begin{document} \title{On the Size of Convex Hulls of Small Sets} \author{\name Shahar Mendelson \email shahar@csl.anu.edu.au \\ \addr Computer Sciences Laboratory\\ Research School of Information Sciences and Engineering\\ The Australian National University\\ Canberra 0200, Australia } \editor{Dana Ron} \maketitle \begin{abstract}% We investigate two different notions of ``size" which appear naturally in Statistical Learning Theory. We present quantitative estimates on the {\it fat-shattering dimension} and on the covering numbers of convex hulls of sets of functions, given the necessary data on the original sets. The proofs we present are relatively simple since they do not require extensive background in convex geometry. \end{abstract} \begin{keywords} Convex hulls, fat-shattering dimension, covering numbers \end{keywords} \section{Introduction} Convexity plays an important role in Machine Learning. Its significance can be seen in both sides of Learning Theory. Firstly, from the practitioner's point of view, minimizing empirical risks is much easier when the class is convex. Secondly, from the theoretical standpoint, the sample complexity needed for agnostic learning is considerably smaller for convex classes \citep{LBW,COLT01a}. On the other hand, if the original class one is interested in happens to be non-convex, taking the convex hull increases the size of the class and it is not clear whether this is worth the effort, since the benefits of learning from a convex class might be negligible compared to the price one has to pay for using the much larger class. Thus, it is natural to ask ``how large" can a convex hull of a given class be? We shall present an answer with respect to two important parameters which measure the size of a class: the covering numbers and the fat-shattering dimension. The estimates on the covering numbers we present are not new and have recently appeared in \cite{CKP}. The main reason we chose to present an alternative proof is because the one in \cite{CKP} uses very deep results in the local theory of Banach spaces, hence it is less accessible to the non expert reader. The proof we present here is self contained and (almost) does not assume any prior knowledge. \par The upper bound on the fat-shattering dimension of the convex hull of a class uses a notion originating from Banach spaces theory called {\it type}. This is a property of some Banach spaces which appears naturally when trying to compute the fat-shattering dimension of linear functionals \citep{Gurvits,Men98}. The path we take is as follows: we begin by improving the known upper bounds on the fat-shattering dimension of the functionals $\{x^*| \norm{x^*} \leq 1\}$ (defined below) when considered as functions on the unit ball of the space. It turns out that this linear fat-shattering dimension is determined by the {\it type} of the Banach space. We use this fact to prove the results concerning the fat-shattering dimension of a convex hull of a general class. To that end, we embed both the class and the shattered set into two finite dimensional Banach spaces, where the dimension of the spaces is the size of the shattered set. The unit ball of the first space is the symmetric convex hull of the $n$-tuples $\bigl(f(\om_i)\bigr)_{i=1}^n$ where $f \in F$ and $(\om_i)_{i=1}^n$ is the shattered set. The second Banach space is the dual space to the first. It is possible to show that the fat-shattering dimension of a given class may be controlled by the fat-shattering dimension of the embedded class, only now, its members are considered as linear functionals on the images of $(\om_i)_{i=1}^n$. Thus, it is possible to bound the fat-shattering dimension using ``linear" methods. \par The article is divided into two main sections. In section \ref{entropy} we prove the covering numbers estimate. Section \ref{typesec} is devoted to the investigation of the linear fat-shattering dimension and the fat-shattering of convex hulls. %\par \subsection{Basic results, definitions and notation} \par \noindent Given a Banach space $X$, the {\it dual} of $X$, denoted by $X^*$, consists of all the bounded linear functionals on $X$, endowed with the norm \begin{equation*} \norm{x^*}_{X^*}=\sup_{\norm{x}_X=1}\abs{x^*(x)}. \end{equation*} We denote the unit ball of $X$ by $B(X)$ and the dual unit ball by $B(X^*)$. If $1 \leq p< \infty$, let $\ell_p^n$ be $\R^n$ equipped with the norm $\norm{x}_p =\bigl(\sum_{i=1}^n \abs{x_i}^p \bigr)^{1/p}$ and set $\ell_\infty^n$ to be $\R^n$ with respect to the sup norm. \par Given a set $A$, let $A^c$ be its complement, set $\abs{A}$ to be its cardinality and denote its characteristic function by $\chi_A$. Thus, $\chi_A(x)=1$ if $x \in A$ and $0$ otherwise. If $A$ and $B$ are sets, let $A+B=\{a+b|a\in A, b \in B\}$. \par For any probability measure $\mu$ on a measurable space $(\Omega,\Sigma)$, let $\E_\mu$ denote the expectation with respect to $\mu$. $L_p(\mu)$ is the set of functions which satisfy $\E_\mu \abs{f}^p < \infty$ and set $\norm{f}_{L_p(\mu)}=(\E_\mu \abs{f}^p)^{1/p}$. Given $I \subset \Omega$, $L_\infty(I)$ is the space of bounded functions on $I$, with respect to the norm $\norm{f}_\infty =\sup_{\omega \in I} \abs{f(\omega)}$. For every $\omega \in \Omega$ let $\delta_\omega$ be the point evaluation functional, that is, for every function $f$ on $\Omega$, $\delta_\omega(f)=f(\omega)$. We denote by $\mu_n$ an empirical measure supported on a set of $n$ points, hence, $\mu_n=\frac{1}{n}\sum_{i=1}^n \delta_{\omega_i}$. If $\abs{I}=n$ and $\mu_n$ is the empirical measure supported on $I$, we denote $L_\infty(I)$ by $L_\infty(\mu_n)$. \par Throughout this paper, all absolute constants are denoted by $C$ or $c$. Their values may change from line to line or even within the same line. \par The following are the definitions of well known combinatorial parameters which are often used in Learning Theory. \begin{Definition} \label{VCdef} Let $\Eff$ be a class of $\{0,1\}$-valued functions on a space $\Omega$. We say that $\Eff$ shatters $\{\omega_1,...,\omega_n\} \subset \Omega$, if for every $I \subset \{1,...,n \}$ there is a function $f_I \in \Eff$ for which $f_I(\omega_i) =1$ if $i \in I$ and $f_I(\omega_i)=0$ if $ i \not \in I$. Let \begin{equation*} VC(\Eff,\Omega)=\sup \Bigl\{\abs{A} \Big| A \subset \Omega, \ A \ {\rm is \ shattered \ by} \ \Eff \Bigr\}. \end{equation*} $VC(\Eff,\Omega)$ is called the VC dimension of $\Eff$. \end{Definition} There is a parametric version of the VC dimension, called the fat-shattering dimension: % \begin{Definition} For every $\eps>0$, a set $A=\{ \omega_1,...,\omega_n \} \subset \Omega$ is said to be $\eps$--shattered by $F$ if there is some function $s:A \to \R$, such that for every $I \subset \{1,...,n\}$ there is some $f_I \in F$ for which $f_I(\omega_i) \geq s(\omega_i)+\eps$ if $i \in I$, and $f_I(\omega_i) \leq s(\omega_i)-\eps$ if $i \not \in I$. Let \begin{equation*} {\rm fat}_\eps(\Eff,\Omega)=\sup \Bigl\{\abs{A} \Big| A \subset \Omega, \ A \ {\rm is} \ \eps{\rm -shattered \ by} \ \Eff \Bigr\}. \end{equation*} The set $\bigl(s_i \bigr)=\bigl(s(\om_i)\bigr)$ is called a witness to the shattering and for every $I \subset \{1,...,n\}$ we call $f_I$ the shattering function of the set $I$. In cases where the set $\Omega$ is clear, we will denote the fat-shattering dimension by ${\rm fat}_\eps(F)$. \end{Definition} \par If $(X,d)$ is a metric space and if $\Eff \subset X$, let $N(\eps,\Eff, d)$ be the minimal number of open balls with radius $\eps>0$ (with respect to the metric $d$) needed to cover $\Eff$. The numbers $N(\eps,\Eff,d)$ are called the covering numbers of $\Eff$. A set $A \subset X$ is said to be an $\eps$-cover of $\Eff$ if the union of open balls $\bigcup_{a \in A} B(a,\eps)$ contains $\Eff$. In cases where the subset ${\Eff}$ is obvious, we denote the covering numbers by $N(\eps,d)$. In cases where the metric is clear we denote the covering numbers by $N(\eps,{\Eff})$. The logarithm of the covering numbers of a set is sometimes called the {\it entropy} of the set. \par A set is called $\eps$-separated if the distance between any two elements of the set is larger than $\eps$. Set $D(\eps,\Eff)$ to be the maximal cardinality of an $\eps$-separated set in $\Eff$. It is easy to see that $N(\eps,\Eff) \leq D(\eps,\Eff) \leq N(\eps/2,\Eff)$. \par % % The following result, which is due to \citet*{ABCH}, enables one to estimate the $L_\infty(\mu_n)$ covering numbers of classes in terms of the fat-shattering dimension. \begin{Theorem} \label{ABCH} Let $\Eff$ be a class of functions from $\Omega$ into $[0,1]$ and set $d=\ff{\eps/4}$. Then, for every empirical measure $\mu_n$ on $\Omega$, \begin{equation*} D{\bigl(\eps, F, L_\infty(\mu_n) \bigr)} \leq 2\Bigl(\frac{4n}{\eps^2}\Bigr)^{d\log{\bigl(en/(d\eps)\bigr)}}. \end{equation*} \end{Theorem} %\par \subsection{The main results} We end this introduction with a summary of the main results presented in the sequel which are relevant in the context of Machine Learning. \par In the next section, we present a general estimate on the $L_2$ covering numbers of convex hulls of a class, given the covering numbers of the class. As a corollary of that result we obtain the following: \begin{Theorem} Let $F$ be a class of functions on $\Omega$. \begin{description} \item{1.} There is an absolute constant $C$ such that for every VC class of functions $F$, every probability measure $\mu$ on $\Omega$ and every $\eps>0$, \begin{equation*} \log N \bigl(\eps,{\rm conv}(F),L_2(\mu)\bigr) \leq Cd\Bigl(\frac{1}{\eps}\Bigr)^{\frac{2d}{d+1}}, \end{equation*} where ${\rm VC}(F)=d$. \item{2.} If $F$ maps $\Omega$ into $[0,1]$ and ${\rm fat}_\eps(F) \leq \gamma\eps^{-p}$ for some $p<2$ and $\gamma>0$, then for every $p0$, \begin{equation*} \log N \bigl(\eps,{\rm conv}(F),L_2(\mu)\bigr) \leq \frac{C}{\eps^2}\log^{1-\frac{2}{p'}} \frac{1}{\eps}. \end{equation*} \end{description} \end{Theorem} \par In the final section we investigate the fat-shattering dimension of convex hulls. In particular, we prove the following: \begin{Theorem} There is an absolute constant $C$, such that for every class $F$ which consists of functions which map $\Omega$ into $[0,1]$ and every $\eps>0$, \begin{equation*} {\rm fat}_\eps \bigl({\rm conv}(F)\bigr) \leq C\frac{{\rm fat}_{\frac{\eps}{4}}(F)}{\eps^2}\log^2 \Bigl(\frac{2{\rm fat}_{\frac{\eps}{4}}(F)}{\eps}\Bigr). \end{equation*} \end{Theorem} \section{Entropy of convex hulls of classes} \label{entropy} In this section we provide estimates on the entropy of convex hulls of classes when considered as subsets of $L_2$ spaces. We divide our discussion into two parts. First, we deal with classes of $\{0,1\}$-valued functions which have a finite VC dimension. Then, we investigate classes of functions with a uniformly bounded range for which the fat-shattering dimension is polynomial in ${\eps}^{-1}$. \par The path we take is rather general. We estimate the covering numbers of a convex hull of a set, given that the covering numbers of the set itself are polynomial in ${\eps}^{-1}$. We combine this general result with well known bounds on the covering numbers of classes using the fat-shattering dimension, thus obtaining the desired entropy estimate. \par \subsection{General Estimates} We shall investigate two generic cases. The first is when $N\bigl(\eps,\Eff,L_2(\mu)\bigr)=O(\eps^{-p})$ for some $p>0$, and the second, (which is more difficult), when $\log N\bigl(\eps,\Eff,L_2(\mu)\bigr)=O(\eps^{-p})$ for $0 < p <2$. The first case was investigated by \citet{Dud87}. He showed that for every $\delta>0$, the log-covering numbers of the convex hull of $\Eff$ are polynomial in ${\eps}^{-1}$ with exponent $\delta+ 2p(p+2)^{-1}$ . This result was improved independently by \citet{VW} and by \citet{Carl97} who removed the superfluous $\delta$. Those results indicate that if $N\bigl(\eps,\Eff,L_2(\mu)\bigr) \leq \gamma\eps^{-p}$ for some $\gamma>0$ and $p>0$, and if $K$ is the symmetric convex hull of $\Eff$, then the entropy integral $\int_0^1 \log^{1/2} N\bigl(\eps,K,L_2(\mu)\bigr)d\eps$ converges. This fact is very significant, since this integral measures in some sense how ``large" the class is. For example, classes with bounded entropy integrals satisfy the {\it uniform central limit theorem} \citep[see][]{Dudley99}. \par On the other hand, from the quantitative point of view, there were no estimates on the constant $C=C(\gamma,p)$ for which \begin{equation*} \log N\bigl(\eps,K,L_2(\mu)\bigr) \leq C\Bigl(\frac{1}{\eps}\Bigr)^{ \frac{2p}{p+2}}. \end{equation*} Note that from the Machine Learning point of view, the constant is significant, since for VC classes the exponent $p$ is half the VC dimension of the class. Hence, it is only natural to try and find the way in which the constant depends on $p$. Another natural question which Dudley's assertion raises is whether similar results may be obtained even when the covering numbers are considerably larger. For example, does the entropy integral of the symmetric convex hull of $\Eff$ converge if $\log N\bigl(\eps,\Eff,L_2(\mu)\bigr)=O(\eps^{-p})$ for some $00$ such that $N\bigl(\eps,\Eff,L_2(\mu)\bigr) \leq \gamma \eps^{-p}$ for every $\eps>0$, then there is an absolute constant $C$ such that for every $\eps>0$, \begin{equation*} \log N\bigl(\eps,K,L_2(\mu)\bigr) \leq C\gamma^{\frac{2}{p}}p \Bigl(\frac{1}{\eps}\Bigr)^{\frac{2p}{2+p}}. \end{equation*} \item{{\rm 2.}} If there are $\gamma>0$ and $00$, then there is some constant $C(p,\gamma)$ (which depends only on $p$ and $\gamma$), such that \begin{equation*} \log N\bigl(\eps,K,L_2(\mu)\bigr) \leq C(p,\gamma) \frac{1}{\eps^2}\log^{1-\frac{2}{p}}\frac{1}{\eps}. \end{equation*} In particular, the entropy integral of $K$ converges for $p<2/3$. \end{description} \end{Theorem} An estimate on the growth rate of the entropy numbers recently appeared in \cite{CKP}, using very deep results in the local theory of Banach spaces. The significance of the proof we present here is the fact that it does not use the powerful machinery of convex geometry, hence, it is more accessible. \par We present a complete proof of the second claim. The proof of the first assertion follows the same path and some of the details are omitted. Both proofs are based on an idea which was used in \citet[pg.~142]{VW}, and in fact, the first claim follows from a careful analysis of the proof in \cite{VW}. \par % We shall require three preliminary results. The first result is due to B. Maurey, appeared in \citep{Maurey}, and is interesting by itself. \begin{Lemma} \label{maurey} Let $\Eff \subset L_2(\mu)$ be a set of $n$ functions and denote its diameter by ${\rm diam}(\Eff)$. Then, for every $\eps>0$, \begin{equation*} N\bigl(\eps {\rm diam}(\Eff), {\rm conv}(\Eff), L_2(\mu)\bigr) \leq (e+en\eps^2)^{\frac{2}{\eps^2}}. \end{equation*} \end{Lemma} \par \noindent Let $(\delta_i)_{i=1}^\infty$ be a positive sequence decreasing to $0$ and set $\Eff_i$ to be an increasing family of sets, such that for every $i$, $\Eff_i$ is a $\delta_i$-separated set in $\Eff$ which is maximal with respect to inclusion (that is, each $\Eff_i$ is $\delta_i$-separated and if $\Eff_i \subset A \subset \Eff$ then $A$ is not $\delta_i$-separated). Note that in our case, each one of the sets $\Eff_i$ is finite. \par For every $i>j$ and every $x \in \Eff_i$, let $P_jx$ be a member of $\Eff_j$ which is nearest to $x$ and put $G_{ij}=\{ x-P_jx \ | \ x \in \Eff_i \}$. \par \begin{Lemma} \label{conv} For every $i>j \geq 1$ and every $\eps,\eps'>0$, \begin{equation*} \conv (\Eff_i) \subset \conv (\Eff_j) + \conv (G_{ij} \cup \{0\}), \end{equation*} and \begin{equation*} N(\eps,\conv(\Eff_i)) \leq \Bigl(1+\frac{4\eps'}{\eps} \Bigr) ^{\abs{\Eff_j}}N\bigl(\eps',\conv(\Eff_j)\bigr) \Bigl(e+e\abs{\Eff_i} \frac{\eps^2}{16\delta_j^2} \Bigr)^{32\delta_j^2/\eps^2}. \end{equation*} \end{Lemma} \par \noindent {\bf Proof:} Clearly, the cardinality $\abs{G_{ij} \cup \{0\}} \leq \abs{\Eff_i}-\abs{\Eff_j}+1$ and, since $\Eff_j$ is a maximal $\delta_j$-separated set in $\Eff$, then for every $x \in \Eff$, $\norm{x-P_jx} \leq \delta_j$. \par Set $\Eff_i=\{x_1,...,x_{\abs{\Eff_i}}\}$ and $\Eff_j =\{x_1,...,x_{\abs{\Eff_j}} \} \subset \Eff_i$. If $z \in \conv(\Eff_i)$, then there are $\lambda_i \geq 0$ such that $\sum_{i=1}^{\abs{\Eff_i}} \lambda_k=1$ and \begin{equation*} z=\sum_{k=1}^{\abs{\Eff_i}} \lambda_k x_k = \sum_{k=1}^{\abs{\Eff_j}} \lambda_kx_k +\sum_{k=\abs{\Eff_j}+1}^{\abs{\Eff_i}} \lambda_k P_jx_k+ \sum_{k=\abs{\Eff_j}+1}^{\abs{\Eff_i}} \lambda_k(x_j-P_jx_k)=z_1+z_2 \end{equation*} where $z_1 \in \conv(\Eff_j)$ and $z_2 \in \conv(G_{ij} \cup \{0\})$. Hence, \begin{equation*} \conv(\Eff_i) \subset \conv(\Eff_j)+\conv(G_{ij} \cup \{0\}) \end{equation*} and the first assertion is verified. \par It is routine to see that if $A,B,C \subset L_2(\mu)$ are such that $A \subset B+C$, then for every $\eps_1,\eps_2>0$, \begin{equation*} N(\eps_1+\eps_2,A) \leq N(\eps_1,B) \cdot N(\eps_2,C). \end{equation*} Thus, by the first claim it follows that \begin{equation} \label{mul} N(\eps,\conv(\Eff_i)) \leq N\bigl(\frac{\eps}{2},\conv(\Eff_j)\bigr) \cdot N\bigl(\frac{\eps}{2},\conv(G_{ij} \cup \{0\})\bigr). \end{equation} To estimate the first term, note that ${\rm span}(\Eff_j)$ can be isometrically embedded in $\ell_2^{\abs{\Eff_j}}$. Therefore, the covering numbers of $\Eff_j$ in $L_2(\mu)$ and in $\ell_2^{\abs{\Eff_j}}$ are the same. Let ${\cal B}$ be the unit ball in $\ell_2^{\abs{\Eff_j}}$. Using a standard volume estimate \citep[see][]{Pisier89}, one can show that for every $\eps,\eps'$, \begin{equation*} N(\frac{\eps}{2},\eps'{\cal B}) \leq \Bigl(1+\frac{4\eps'}{\eps}\Bigr)^{\abs{\Eff_j}}. \end{equation*} Hence, \begin{align*} N\bigl(\frac{\eps}{2},\conv(\Eff_j)\bigr) & \leq N\bigl(\frac{\eps}{2},\eps'{\cal B}\bigl) \cdot N\bigl(\eps',\conv(\Eff_j)\bigr) \\ & \leq \Bigl(1+\frac{4\eps'}{\eps} \Bigr)^{\abs{\Eff_j}} \cdot N\bigl(\eps',\conv(\Eff_j)\bigr). \end{align*} As for the second term in (\ref{mul}), since ${\rm diam}(G_{ij} \cup \{0\}) \leq 2\delta_j$ and $\abs{G_{ij} \cup \{0\}} \leq \abs{\Eff_i}$, then by Lemma \ref{maurey} \begin{align*} N\Bigl(\frac{\eps}{2},\conv \bigl(G_{ij} \cup \{0\} \bigr) \Bigr) & = N\Bigl(\frac{\eps}{4\delta_j}2\delta_j,\conv \bigl( G_{ij} \cup \{0\} \bigr) \Bigr) \\ & \leq \Bigl(e+e\abs{\Eff_i} \frac{\eps^2}{16\delta_j^2}\Bigr) ^{32\delta_j^2/\eps^2}. \end{align*} \par \rightline{$\blacksquare$} \par Lemma \ref{conv} reveals our strategy which is similar in nature to chaining. Here, we create an increasing family of sets which form an increasingly finer approximation of $F$. It is possible to estimate the covering numbers of the convex hulls of the ``finer" sets using an estimate on the ``coarser" sets. The rates by which the mesh of the classes $F_i$ decreases will be dictated by the growth rates of the covering numbers in the class $F$. In the next two technical results we select an appropriate rate of decay for the ``mesh" sequence $(\delta_n)$. \par \begin{Lemma} \label{sequences1} Let $\Eff$ be a subset of the unit ball in $L_2(\mu)$ and assume that there are constants $\gamma,p>0$, such that for every $\eps>0$, \begin{equation*} N\bigl(\eps,\Eff,L_2(\mu)\bigr) \leq \gamma \Bigl(\frac{1}{\eps} \Bigr)^{p}. \end{equation*} Let $\delta_n=\gamma^{1/p}n^{-1/p}$ and set $\Eff_n$ to be as in Lemma \ref{conv}. Then, there are bounded sequences $(A_k)$ and $(B_k)$ such that for every $n$ and $k$, \begin{equation} \log N \bigl(A_k n^{\frac{1}{2}}\delta_n,{\rm conv} (\Eff_{nk^{3p}})\bigr) \leq B_kn. \end{equation} Moreover, there are absolute constants $A$ and $B$ such that for every $k$, $A_k \leq \gamma^{1/p}A$ and $B_k \leq Bp$. \end{Lemma} \begin{Lemma} \label{sequences2} Let $\Eff$ be a subset of the unit ball of $L_2(\mu)$ and assume that there are $\gamma>0$ and $00$, \begin{equation*} \log N\bigl(\eps,\Eff,L_2(\mu) \bigr) \leq \gamma\eps^{-p}. \end{equation*} Set $\delta_n=2\gamma^{1/p}\log^{-1/p}n$, $\eps_n=n^{-1}\log^{1/p}n$ and let $\Eff_n$ be as in Lemma \ref{conv}. Then, there are sequences $(A_k)$ and $(B_k)$ which depend on $p$, such that for all integers $n \geq 2$ and $k \geq 1$ \begin{equation*} \log N \bigl(A_k\eps_n, \conv (\Eff_{[n^{k^\alpha}]}) \bigr) \leq B_k \frac{n^2}{\log^{\frac{4}{p}-1}n}, \end{equation*} where $\alpha=4p/(2-p)$ and $[x]$ denotes the integer value of $x$. Moreover, $\sup A_k \leq A_p'$ and $\sup B_k \leq B_p'$ for some constants $A_p'$ and $B_p'$ which depend only on $p$. \end{Lemma} \par We present a complete proof of Lemma \ref{sequences2}. The proof of Lemma \ref{sequences1} follows from a similar argument. The idea behind the proof of Lemma \ref{sequences1} is due to \citet{VW}. The quantitative estimate on the constants does not appear in that text, but may be derived by a close analysis of the proof the authors present. \par \vskip 0.4cm \noindent {\bf Proof of Lemma \ref{sequences2}:} We use a nested induction argument. First, we prove our claim for $k=1$ using induction on $n$. We then prove the claim for a general $k$ for every fixed $n$. \par Recall that for every integer $n$, $\Eff_n$ is maximal $\delta_n$ separated in $\Eff$. Thus \begin{equation*} \abs{\Eff_n} \leq N(\frac{\delta_n}{2},\Eff) \leq e^{\gamma(2/\delta_n)^p}=n. \end{equation*} \par Let $n_0 \geq 4$ be an integer such that for every $n \geq n_0$, \begin{equation*} \frac{ \iger{ \frac{n}{2} }^2}{\log^{\frac{4}{p}-1}\iger{ \frac{n}{2} }} \leq \frac{3}{4}\frac{n^2}{\log^{\frac{4}{p}-1}n}. \end{equation*} Let $k=1$ and $2 \leq n \leq 2n_0$ and set $A_1=2n_0\log^{-1/p}2n_0$. Since for such a value of $n$, $A_1\eps_n \geq 1$, only a single ball is required to cover $\Eff$ and our claim follows. \par Next, let $n > 2n_0$ and assume that for every $2 \leq m 0$ and $0p$ there is some constant $C=C(p,p',\gamma)$ such that for every probability measure $\mu$, \begin{equation*} \log N\bigl(\eps,{\rm conv}(F),L_2(\mu)\bigr) \leq C\frac{1}{\eps^2}\log^{1-\frac{2}{p'}} \frac{1}{\eps}. \end{equation*} \end{Corollary} % % % % % \section{Type and the fat-shattering dimension} \label{typesec} In this section, we tackle the problem of estimating the fat-shattering dimension of convex hulls of classes. To that end, we first deal with ``linear" fat-shattering dimension. By this we mean the fat-shattering dimension of a set of linear functionals, for example, the unit ball of the dual space of some Banach space, when considered to be a class of functions on the unit ball of the space. As it turns out, given a Banach space $X$, the fat-shattering dimension of the set $B(X^*)$ when considered as functions on $B(X)$ is completely determined by a property of $X$ called {\it type} (defined below). \par The results we present aid our goal since one can apply an embedding argument to show that, in some sense, the fat-shattering dimension of a given class may be controlled by the fat-shattering dimension of a class of linear functionals. \par In order to bound the fat-shattering dimension of convex hulls we take the following course of action: first, we apply the embedding argument, which reduces the problem to a ``linear" one. Then, we show that the symmetric convex hull of the embedded class can be approximated by a class which has ``almost" the same fat-shattering dimension, but also a well behaved type structure. This is done by using an estimate on the covering numbers of the class with respect to the $L_\infty$ norm. The fat-shattering of the approximating class may be bounded via the bound on ${\rm fat}_\eps \bigl(B(X^*),B(X)\bigr)$ mentioned above. \par Before we continue, we require additional definitions, originating in the theory of Banach spaces. For the basic definitions we refer the reader to \citep{Pisier89} or \citep{TJ}. \par Let $K$ be a bounded, convex symmetric subset of $\R^n$ which has a nonempty interior. One can define a norm on $\R^n$ whose unit ball is $K$. This is done using the Minkowski functional on $K$, which is denoted by $\norm{ \ }_K$, and given by \begin{equation*} \norm{x}_K=\inf \{t>0 | t^{-1}x \in K \}. \end{equation*} It is possible to show that if $K \subset \ell_2^n$ is convex and symmetric with a nonempty interior then $\norm{ \ }_K$ is indeed a norm and $K$ is its unit ball. Set $\norm{ \ }_{K^*}$ to be the dual norm to $\norm{ \ }_K$. \begin{Definition} \label{polar} If $F$ is a bounded subset of $\ell_2^n$, let \begin{equation*} F^{\rm o}=\{x \in \ell_2^n | \sup_{f \in F} \abs{\inr{f,x}} \leq 1 \}, \end{equation*} where $\inr{-,-}$ is the inner product in $\ell_2^n$. The set $F^{\rm o}$ is called the polar of $F$. \end{Definition} For any set $F$, let ${\rm absconv}(F)$ be its symmetric convex hull. Formally, \begin{equation*} \aconv(F)=\Bigl\{\sum_{i=1}^n a_if_i | n \in \N, f_i \in F, \sum_{i=1}^n \abs{a_i}=1 \Bigr\}. \end{equation*} \par It is easy to see that $F^o=\bigl({\rm absconv}(F)\bigr)^o$ and that if $G \subset F$ then $F^o \subset G^o$. Note that $F^o$ is the unit ball of the norm $\norm{ \ }_{K^*}$, where $K={\rm absconv}(F)$. Hence, for every $x \in \ell_2^n$, \begin{equation*} \norm{x}_{F^o}=\sup_{y \in {\rm absconv(F)}} \inr{y,x}=\sup_{y \in F} \abs{\inr{y,x}}. \end{equation*} In particular, if $F=\{f_1,...,f_m\}$ then $\norm{x}_{F^o}=\max_{1 \leq i \leq m} \abs{\inr{f_i,x}}$. \par Given a class $F$ and an empirical measure $\mu_n$ supported on $\{\om_1,...,\om_n\}$, we endow $\R^n$ with the Euclidean structure of $L_2(\mu_n)$, which is isometric to $\ell_2^n$. Therefore, for every $f \in L_2(\mu_n)$, \begin{equation*} \norm{f}_{L_2(\mu_n)}=\Bigl(\frac{1}{n}\sum_{i=1}^n f^2(\om_i)\Bigr)^{\frac{1}{2}}. \end{equation*} Let $F/\mu_n$ be the image of $F$ in $L_2(\mu_n)$ under the inclusion operator, that is, \begin{equation*} F/\mu_n= \Bigl\{\sum_{i=1}^n f(\om_i)\chi_{\{\om_i\}} | f \in F \Bigr\}. \end{equation*} Since $(n^{1/2}\chi_{\{\om_i\}})_{i=1}^n$ is an orthonormal basis of $L_2(\mu_n)$, then \begin{equation*} F/\mu_n=\Bigl\{n^{-\frac{1}{2}}\sum_{i=1}^n f(\om_i)e_i | f \in F\Bigr\}. \end{equation*} \par Throughout this section, given an empirical measure $\mu_n$, we denote by $(e_i)_{i=1}^n$ the orthonormal basis of $L_2(\mu_n)$ given by $(n^{1/2}\chi_{\{\om_i\}})_{i=1}^n$. \par The next lemma is straightforward and its proof is omitted. \begin{Lemma} \label{shattering} Let $S=\{\om_1,...,\om_n\}$ be a sample and let $\mu_n$ be the empirical measure supported on $S$. \begin{description} \item{1.} If $S$ is shattered by $\Eff$ then the set $\{\sqrt{n}e_1,...,\sqrt{n}e_n\} \subset (\Eff/\mu_n)^o$ is shattered by $\Eff/\mu_n$. \item{2.} If $S$ is $\eps$-shattered by $\Eff$ then $\{\sqrt{n}e_1,...,\sqrt{n}e_n\} \subset (\Eff/\mu_n)^o$ is $\eps$-shattered by $\Eff/\mu_n$. \end{description} \end{Lemma} % % % \par \subsection{The fat-shattering dimension of linear functionals} Recall the definition of the Rademacher type of a Banach space: \begin{Definition} A Banach space $X$ has Rademacher type $p$ if there is some $C$ such that for every integer $n$ and every $x_1,...,x_n \in X$, \begin{equation} \label{radtype} \E \norm{ \sum_{i=1}^n \eps_i x_i} \leq C \Bigl( \sum_{i=1}^n \norm{x_i}^p \Bigr)^{1/p}, \end{equation} where $(\eps_i)$ are independent Rademacher random variables (i.e., symmetric $\{-1,1\}$-valued). The best constant for which (\ref{radtype}) holds is called the Rademacher $p$-type constant of $X$ and is denoted by $T_p(X)$. \end{Definition} \begin{Theorem} \label{lvc} Let $X$ be a Banach space which has type $p$ for some $1 < p \leq 2$ with a type constant $T_p(X)$. Then \begin{equation*} {\rm fat}_\eps \bigl(B(X^*),B(X)\bigr) \leq \Bigl(\frac{T_p(X)}{\eps}\Bigr)^{\frac{p}{p-1}}. \end{equation*} \end{Theorem} Note that a similar result to this was demonstrated by \cite{Gurvits}, though in his result the bound is on the level fat-shattering dimension (that is, the witness $(s_i)_{i=1}^n$ to the shattering is a constant set: there is some $a$ such that $s_i=a$ for every $1 \leq i \leq n$). \par \vskip 0.4cm \noindent {\bf Proof:} Assume that the set $\{x_1,...,x_n\} \subset B(X)$ is $\eps$-shattered by $B(X^*)$ and set $\{s_1,...,s_n\}$ to be a witness to the shattering. Let $I \subset \{1,...,n\}$ and put $x^*_I$ to be the functional shattering the set $I$. Note that if $i \in I$ then \begin{equation*} x^*_I(x_i)-x^*_{I^c}(x_i) \geq s_i+\eps-(s_i-\eps)=2\eps, \end{equation*} and if $i \in I^c$, \begin{equation*} x^*_{I^c}(x_i)-x^*_{I}(x_i) \geq s_i+\eps-(s_i-\eps)=2\eps. \end{equation*} Thus, \begin{align*} & \norm{ \Bigl(\sum_{i \in I} x_i-\sum_{i \in I^c} x_i \Bigr)} =\sup_{x^* \in B(X^*)} \abs{x^*\Bigl(\sum_{i \in I} x_i-\sum_{i \in I^c} x_i \Bigr)} \\ & \geq \frac{1}{2} \sup_{x^*,\tilde{x}^* \in B(X)} \abs{x^*\Bigl(\sum_{i \in I} x_i-\sum_{i \in I^c} x_i \Bigr)-\tilde{x}^*\Bigl(\sum_{i \in I} x_i-\sum_{i \in I^c} x_i \Bigr)}=(*) \end{align*} Selecting $x^*=x^*_I$ and $\tilde{x}^*=x^*_{I^c}$, \begin{align*} (*) & \geq \frac{1}{2} \abs{x^*_I\Bigl(\sum_{i \in I} x_i-\sum_{i \in I^c} x_i \Bigr)-x^*_{I^c}\Bigl(\sum_{i \in I} x_i-\sum_{i \in I^c} x_i \Bigr)} \\ & =\frac{1}{2} \abs{\sum_{i \in I} \bigl(x^*_I(x_i)-x^*_{I^c}(x_i) \bigr) + \sum_{i \in I^c} \bigl(x^*_{I^c}(x_i)-x^*_{I}(x_i) \bigr)} \\ & \geq \frac{1}{2} \bigl(2\eps\abs{I}+2\eps \abs{I^c} \bigr) = \eps n. \end{align*} % % % Now, we can use the type property to establish an upper bound for an appropriate subset $I$ which will be selected randomly. Indeed, since $X$ has type $p$ and since $\norm{x_i} \leq 1$ then \begin{equation*} \E\norm{\sum_{i=1}^n \eps_ix_i} \leq T_p(X)\bigl(\sum_{i=1}^n \norm{x_i}^p)^{\frac1p} \leq T_p(X)n^{\frac1p}. \end{equation*} Thus, there is a realization of the random variables $(\eps_i)$ for which this inequality holds. Let $I=\{i | \eps_i=1\}$. Then, \begin{equation*} \norm{\sum_{i \in I} x_i - \sum_{i \in I^c} x_i} \leq T_p(X)n^{\frac1p}. \end{equation*} Thus, $n\eps \leq T_p(X)n^{1/p}$ and our claim follows. \par \rightline{$\blacksquare$} \par \begin{Remark} It is possible to show that this bound is tight \citep[see][]{Men98}. Indeed, one can show that if $p^*=\sup\{p| {\rm X \ has \ type} \ p \}$ then for every $\eps>0$, \begin{equation*} \Bigl(\frac{1}{\eps}\Bigr)^{\frac{p^*}{p^*-1}} -1 \leq {\rm fat}_\eps\bigl(B(X^*),B(X)\bigr). \end{equation*} This implies that if $X$ is a Hilbert space then for every $\eps>0$, \begin{equation*} \Bigl(\frac{1}{\eps^2}\Bigr)-1 \leq{\rm fat}_\eps\bigl(B(X^*),B(X)\bigr)\leq \Bigl(\frac{1}{\eps^2}\Bigr). \end{equation*} \end{Remark} % \subsection{Covering numbers and type constants} Here, we show that if the class $F$ is well behaved, (either a VC class or a class with a finite fat-shattering dimension for every $\eps$), then the Rademacher type-2 constant of $(F/\mu_n)^o$ does not grow too rapidly as a function of $n$. \par In order to bound the type-2 constant of $(F/\mu_n)^o$, we use a combination of two facts. The first, which is the only non elementary fact we require, is an estimate on $T_2(\ell_\infty^n)$. It is possible to show \citep{TJ} that there are absolute constants $c$ and $C$ such that for every integer $n$, \begin{equation} \label{ell_inftyT2} c(1+\log{n})^{1/2} \leq T_2(\ell_\infty^n) \leq C(1+\log{n})^{1/2}. \end{equation} The second fact we use is that if the cardinality of $F$ is small then $F^o$ can be isometrically embedded into $\ell_\infty^n$ for a relatively small $n$. \begin{Lemma} \label{iso} Let $F \subset \ell_2^n$ be a finite set. Then $F^o$ can be isometrically embedded into $\ell_\infty^{\abs{F}}$. \end{Lemma} \noindent {\bf Proof:} Let $F=\{f_1,...,f_m\}$ and define $T:(\R^n,\norm{ \ }_{F^o}) \to \ell_\infty^{\abs{F}}$ by $Tx^*=\bigl(x^*(f_i)\bigr)_{i=1}^m$. Then, for every $x^* \in \R^n$ \begin{equation*} \norm{Tx^*}_{\ell^{\abs{F}}_\infty}=\sup_{1 \leq i \leq m} \abs{x^*(f_i)}=\norm{x^*}_{F^o}, \end{equation*} implying that $T$ is an isometry. \par \rightline{$\blacksquare$} \par This fact is very useful from our point of view, since $F/\mu_n$ are relatively small sets. In the real valued case, the $L_\infty(\mu_n)$ covering numbers of $F$ may be bounded using $\ff{\eps}$ (Theorem \ref{ABCH}), whereas for VC classes, one may use the following version of Sauer's Lemma \citep{VW}: \begin{Lemma} \label{Sauer} There is an absolute constant $C$ such that if $F$ is a class of $\{0,1\}$-valued functions on $\Omega$ with $VC(F)=d$, then for every empirical measure $\mu_n$, $\abs{F/\mu_n} \leq Cn^d$. \end{Lemma} Now, we can bound $T_2\bigl((F/\mu_n)^o\bigr)$ for VC classes. In fact, we prove the following: \begin{Theorem} \label{VCandT2} Let $\Eff$ be a class of $\{0,1\}$-valued functions. Then, $\Eff$ is a VC class if and only if there is some constant $C>0$ such that for every integer $n$ and every empirical measure $\mu_n$, $T_2\bigl((F/\mu_n)^o\bigr) \leq C(1+\log{n})^{1/2}$. \end{Theorem} \noindent{\bf Proof:} Note that if $VC(\Eff)=d$ then by Sauer's Lemma there is an absolute constant $C$ such that $\abs{\Eff/\mu_n}\leq Cn^d$. Hence, $(F/\mu_n)^o$ can be isometrically embedded in $\ell_\infty^{Cn^d}$. It follows that $T_2(F^o) \leq C(1+d\log{n})^{1/2} \leq Cd^{1/2}(1+\log n)^{1/2}$ as claimed. \par Conversely, assume that there is a constant $C$ such that for every integer $n$ and every empirical measure $\mu_n$, $T_2((F/\mu_n)^o) \leq C(1+\log{n})^{1/2}$. Let $S=\{\om_1,...,\om_n\}$ be shattered by $\Eff$ and set $\mu_n$ to be the empirical measure supported on $S$. By the first part of Lemma \ref{shattering} and Theorem \ref{lvc}, \begin{equation*} n \leq {\rm fat}_{\frac{1}{2}}((F/\mu_n)^o,F/\mu_n) \leq 4T_2^2\bigl((F/\mu_n)^o \bigr) \leq C(1+\log{n}), \end{equation*} implying that $n$ can not be arbitrarily large, and thus $VC(\Eff,\Omega)<\infty$. \par \rightline{$\blacksquare$} \par \begin{Remark} The proof of theorem \ref{VCandT2} implies that if $\Eff$ is a $\{0,1\}$-valued class such that $\sup_{\mu_n} T_2\bigl( (F/\mu_n)^o \bigr)=o(n)$ then $\Eff$ is a VC class. \end{Remark} Note that the upper bound on $T_2\bigl((F/\mu_n)^o \bigr)$ can not be improved. Indeed, let $\Eff$ be the set of characteristic functions of intervals $[-1,a]$ for $a \in (-1,1]$. Thus, $VC(\Eff)=1$ and for every non degenerate empirical measure $\mu_n$ of $[-1,1]$, \begin{equation*} \Eff/\mu_n=\Bigl\{(1,0,...,0),(1,1,0,...,0),...,(1,1,...,1)\Bigr\}. \end{equation*} Therefore, $(F/\mu_n)^o$ is isometric to $\ell_\infty^n$ and $T_2\bigl((F/\mu_n)^o\bigr) \geq C(1+\log{n})^{1/2}$. \par Also, Theorem \ref{VCandT2} does not apply to classes which are not $\{0,1\}$-valued classes. For example, let $\Omega=B(\ell_p)$ for some $1\eps$ and that $H$ is an $\eps$-cover of $\Eff/\mu_n$ in $L_\infty(\mu_n)$. Then, $A'=\{\sqrt{n}e_1,...,\sqrt{n}e_n\} \subset (F/\mu_n)^o$ is $(\delta-\eps)$-shattered by $H$, where the elements of $H$ are viewed as linear functionals on $(F/\mu_n)^o$. \end{Lemma} \noindent{\bf Proof:} By Lemma \ref{shattering}, $A'$ is $\delta$-shattered by $\Eff/\mu_n$ and set $(s_i)$ to be a witness to the shattering. Fix $I \subset \{1,...,n\}$ and let $f_I \in \Eff/\mu_n$ be the $\delta$-shattering functional on $I$. Put $h_I \in H$ such that $\norm{f_I-h_I}_{L_\infty(\mu_n)} < \eps$. Since $\norm{\sqrt{n}e_i}_{L_1(\mu_n)}=1$ then for every $i \in I$ \begin{align*} \inr{h_I,\sqrt{n}e_i} & =\inr{f_I,\sqrt{n}e_i}+\inr{h_I-f_I,\sqrt{n}e_i} \\ & \geq s_i+\delta- \norm{h_I-f_I}_{L_\infty(\mu_n)}\norm{\sqrt{n}e_i}_{L_1(\mu_n)} \\ & \geq s_i+\delta-\eps, \end{align*} and in a similar fashion, if $j \in I^c$ then %\begin{equation*} $\inr{h_I,\sqrt{n}e_i} \leq s_i-\delta+\eps$, %\end{equation*} and our claim follows. \par \rightline{$\blacksquare$} \par \subsection{The fat-shattering dimension of convex hulls} We begin by formulating the main result, which enables one to estimate the fat-shattering dimension of the convex hull of a class $\Eff$ using the $L_\infty(\mu_n)$ covering numbers of $\Eff$. \par We introduce the following notation. Given a class $\Eff$, an integer $n$ and $\eps>0$, let \begin{equation*} N_\infty(n,\eps)= \sup_{\mu_n} N\bigl(\eps,\Eff,L_\infty(\mu_n)\bigr). \end{equation*} Thus, $N_\infty(n,\eps)$ is the supremum of the $\eps$-covering numbers of $\Eff$ in empirical $L_\infty$ spaces, where the empirical measure is supported on at most $n$ elements of $\Omega$. % % % \begin{Theorem} \label{fatandcover} Let $\Eff$ be a class of functions whose range is a subset of $[0,1]$ and set $K$ to be its symmetric convex hull. Then, for every $\eps,\tau>0$, \begin{equation*} {\rm fat}_{\eps+\tau}\bigl(K,\Omega\bigr) \leq \max \Bigl\{ n| n \leq C\bigl(1+\log N_\infty(n,2\eps)\bigr) \frac{1}{\tau^2} \Bigr\}, \end{equation*} where $C$ is an absolute constant. \end{Theorem} \noindent{\bf Proof:} Fix $\eps, \tau>0$, assume that $A=\{\om_1,...,\om_n\}$ is $(\eps+\tau)$-shattered by $K={\rm absconv}(F)$ and let $\mu_{n}$ be an empirical measure supported on $A$. Let $H \subset \Eff/\mu_{n}$ be an $\eps$-cover to $\Eff/\mu_{n}$ in $L_\infty(\mu_{n})$ and set $G$ to be the symmetric convex hull of $H$. Clearly, $\abs{H} \leq N\bigl(2\eps,F/\mu_n,L_\infty(\mu_n)\bigr)$. \par Since $H$ is an $\eps$-cover of $\Eff/\mu_{n}$ in $L_\infty (\mu_{n})$ then $G$ is an $\eps$-cover to $K$ in $L_\infty(\mu_{n})$. By Lemma \ref{shattering2}, if the set $A$ is $\eps+\tau$ shattered by $K$ then the set $A'=\{\sqrt{n}e_1,...,\sqrt{n}e_{n}\}$ is $\tau$-shattered by $G$, when members of $G$ are viewed as linear functionals on $(F/\mu_n)^o$. Also, note that $A' \subset (F/\mu_n)^o$. Thus, \begin{equation*} n \leq {\rm fat}_\tau\bigl(G,(\sqrt{n}e_i)_{i=1}^n\bigr) \leq {\rm fat}_\tau \bigl(G,(F/\mu_n)^o \bigr). \end{equation*} \par Since $H \subset \Eff/\mu_{n}$, then by taking convex hulls $G \subset K$. Using the properties of the polar, $(F/\mu_n)^o=K^o \subset G^o$, thus ${\rm fat}_\tau \bigl(G,(F/\mu_n)^o\bigr)\leq {\rm fat}_\tau (G,G^o)$. By Lemma \ref{iso} there is an absolute constant $C$ such that \begin{equation*} T_2(G^o) \leq C(1+\log \abs{H})^{\frac{1}{2}} \leq C\Bigl(1+\log N \bigl(2\eps,F/\mu_n,L_\infty(\mu_n)\bigr)\Bigr)^{\frac{1}{2}}. \end{equation*} Hence, by Theorem \ref{lvc}, \begin{equation*} {\rm fat}_\tau (G,G^o) \leq C\Bigl(1+\log N \bigl(\eps,F/\mu_n,L_\infty(\mu_n)\bigr)\Bigr) \frac{1}{\tau^2}. \end{equation*} Therefore, \begin{equation*} n \leq C\Bigl(1+\log N \bigl(2\eps,F/\mu_n,L_\infty(\mu_n)\bigr)\Bigr) \frac{1}{\tau^2}. \end{equation*} \par \rightline{$\blacksquare$} \par % % % % % Applying the known bounds on the $L_\infty(\mu_n)$ covering numbers in terms of the VC or the fat-shattering dimension we can establish the following estimate on the fat-shattering dimension of convex hulls. \begin{Corollary} \label{6.10} There is an absolute constant $C$ such that for every $\{0,1\}$-class of functions and every $\eps,\tau>0$, \begin{equation*} {\rm fat}_{\eps+\tau}(K,\Omega) \leq C \frac{d}{\tau^2}\log{\frac{2d}{\tau}}, \end{equation*} where $K$ is the symmetric convex hull of $\Eff$ and $VC(\Eff)=d$. \par \noindent In particular, there is an absolute constant $C$ such that for every $\tau>0$, \begin{equation*} {\rm fat}_\tau(K,\Omega) \leq C\frac{d}{\tau^2}\log \frac{2d}{\tau}. \end{equation*} \end{Corollary} \par \noindent {\bf Proof:} By Sauer's Lemma, there is an absolute constant $C$ such that for every integer $n$, $\log{N_\infty(n,\eps)} \leq Cd\log{n}$. Fix $\eps,\tau>0$ and let ${\rm fat}_{\eps+\tau}(K,\Omega)=n$. By Theorem \ref{fatandcover}, $n \leq Cd\tau^{-2}(1+\log{n})$ and our claim follows. \par \rightline{$\blacksquare$} \par The best known estimate on the fat-shattering dimension of the convex hull of a VC class is ${\rm fat}_\eps\bigl({\rm conv}(F)\bigr)=O(d/\eps^2)$. This bound is due to \cite{Gurvits} and was obtained using a similar geometric approach to the one presented here. The one key difference between the two approaches is that Gurvits uses a different notion of type. His result is based on an estimate on the type-2 constant of a certain operator, which is due to \citet[Theorem 14.15]{LeTa}. It turns out that their bound depends on the fact that the class $F$ has a converging entropy integral, which is the case for VC classes. \par This approach is not suitable for arbitrary classes of functions, when one does not have a-priori ``global" data (for example, the fat-shattering dimension or covering numbers at every scale), but rather, the fat-shattering dimension at a given scale. It is possible to extend Corollary \ref{6.10} and estimate the fat-shattering dimension of the convex hull of a class using the fat-shattering dimension of the class itself, without resorting to ``global" data. \begin{Theorem} \label{7} There is an absolute constant $C$ such that for any class $\Eff$ of functions into $[0,1]$ and every $\eps,\tau \in (0,1)$, \begin{equation*} {\rm fat}_{\eps+\tau}(K,\Omega) \leq C \frac{ {\rm fat} _{\frac{\eps}{2}}(\Eff,\Omega)} {\tau^2} \log^2{\frac{ 2{\rm fat} _{\frac{\eps}{2}}(\Eff,\Omega)}{\tau^2\eps}} \end{equation*} where $K$ is the symmetric convex hull of $\Eff$. \par \noindent In particular, there is an absolute constant $C$ such that for every $\tau>0$, \begin{equation*} {\rm fat}_{\tau}(K,\Omega) \leq C \frac{ {\rm fat} _{\frac{\tau}{4}}(\Eff,\Omega)} {\tau^2} \log^2{\frac{ 2{\rm fat} _{\frac{\tau}{4}}(\Eff,\Omega)}{\tau}}. \end{equation*} \end{Theorem} \noindent {\bf Proof:} Set $\eps, \delta \in (0,1)$ and let $n={\rm fat}_{2\eps+\tau}(K,\Omega)$. By Theorem \ref{ABCH}, \begin{equation*} \log{N_\infty(n,2\eps)} \leq C {\rm fat}_{\frac{\eps}{2}}(\Eff,\Omega) \log^2{\frac{n}{\eps}}. \end{equation*} Applying Theorem \ref{fatandcover} and since $n>1$ and $\eps \in (0,1)$, there is an absolute constant $C$ such that \begin{equation*} n \leq C\frac{{\rm fat}_{\frac{\eps}{2}}(\Eff,\Omega)}{\tau^2} \log^2{\frac{n}{\eps}}. \end{equation*} Hence, \begin{equation*} n \leq C \frac{{\rm fat}_{\frac{\eps}{2}}(\Eff,\Omega)}{\tau^2} \log^2{ \biggl(\frac{2{\rm fat} _{\frac{\eps}{2}}(\Eff,\Omega)}{\tau^2 \eps}\biggr) }, \end{equation*} and the claim follows. \par \rightline{$\blacksquare$} \par \begin{Remark} Using a different approach it is possible to improve Theorem \ref{7} when one has ``global" data on the fat-shattering dimension of the class. For example, it is possible to recover Gurvits' estimate for the convex hull of VC classes, with a much simpler proof. This approach may be extended to a more general setup. Indeed, if $\ff{\eps}=O(\eps^{-p})$ for $p \not =2$ then ${\rm fat}_\eps \bigl({\rm conv}(F)\bigr)=O\bigl(\eps^{-\max\{2,p\}}\bigr)$. If $p=2$ then ${\rm fat}_\eps \bigl({\rm conv}(F)\bigr)=O(\eps^{-2}\log^4 \frac{1}{\eps})$. This result is demonstrated by analyzing the growth rate of the Rademacher averages associated with the class \citep[see][]{COLT01b} for further details). \end{Remark} \bibliography{crap} \end{document}