\documentclass[twoside,11pt]{article}
\usepackage{jmlr2e}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amscd}

\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{\one}{{\rm 1}\!{\rm I}}
\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{\cL}{{\cal L}}
\newcommand{\cH}{{\cal H}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\T}{{\bf T}}
\newcommand{\HH}{{\cal H}}
\newcommand{\eps}{\varepsilon}
\newcommand{\spec}{\mathop{\rm}}
\newcommand{\ord}{\mathop{\rm ord}}
\newcommand{\MM}{{\cal M}}
\newcommand{\conv}{\mathop{\rm conv}}
\newcommand{\VC}{{\rm VC}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\LL}{{\rm I}\!{\rm L}}
\newcommand{\BB}{{\rm I}\!{\rm B}}
\newcommand{\Eff}{{\cal F}}
\newcommand{\om}{\omega}
\newcommand{\Ell}{\cal L}
\newcommand{\s}{\sigma}
\newcommand{\X}{{X}}
\newcommand{\Y}{{Y}}
\newcommand{\D}{{M}}

% 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{\fg}[1]{{\rm fat}_{#1}(G)}
\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{\Radp}{\bigl(\E \sup_{f \in F} \bigl{|} \sum_{i=1}^n \eps_i f(X_i)
\bigr{|}^p \bigr)^{\frac{1}{p}}}
\newcommand{\Rad}{\E \sup_{f \in F} \bigl{|} \sum_{i=1}^n \eps_i f(X_i)
\bigr{|}}
\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
%\renewcommand{\familydefault}{bch}
\def \endproof
{{\mbox{}\nolinebreak\hfill\rule{2mm}{2mm}\par\medbreak}}
\def \proof {\noindent {\bf Proof.}\ \ }
\newcommand{\pstable}{ $p$-stable }
\newcommand{\Zs}{\ensuremath{\zeta}}
%\newcommand{\pstable}{projection-stable}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% marking parts of text
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% for definitions, etc...
\newcommand{\important}[1]{\underline{\sl #1}}
% for later reference, e.g. unfinished, remarks, etc..
\newcommand{\comment}[1]{({\sl #1})}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% equation delimiters (for convenience)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\BE}{\begin{equation}}
\newcommand{\EE}{\end{equation}}
\newcommand{\BA}{\begin{align}}
\newcommand{\EA}{\end{align}}
\newcommand{\BM}{\begin{multline}}
\newcommand{\EM}{\end{multline}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% mathematical stuff 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Xind}[2][n]{\ensuremath{#2_{i=1}^#1}}

\newcommand{\sample}[2][n]{\ensuremath{(#2_i)_{i=1}^#1}}

\newcommand{\Xdot}[2][n]{\ensuremath{#2_1, #2_2, \dots #2_{#1}}}

% \expect{f} or \expect[X]{f}
\newcommand{\expect}[2][\mu]{\ensuremath{E_{#1}\{ #2 \}}}
% \expects{f} or \expects[X]{f}
\newcommand{\expects}[2][\mu]{\ensuremath{E_{#1} #2 }}

% \mean{f}{X} or \mean[n]{f}{X}
\newcommand{\mean}[3][n]{\ensuremath{\frac{1}{#1} \sum_{i=1}^n {#2} (#3_i )  }}
% \diffmean{f}{X}{Y} or \diffmean[n]{f}{X}{Y}
\newcommand{\diffmean}[4][n]{\ensuremath{\frac{1}{#1} 
\sum_{i=1}^{#1} ({#2} \bigl(#3_i ) -  {#2} (#4_i )\bigr) }}
\newcommand{\absdiffmean}[4][n]{\ensuremath{\Bigl|\diffmean[#1]{#2}{#3}{#4}\Bigr|}}

% fixed and random variables and samples
\newcommand{\fvar}[1]{\ensuremath{\text{#1}}}
\newcommand{\rvar}[1]{\ensuremath{\text{\sf #1}}}
\newcommand{\fsample}[2][n]{\ensuremath{\Xdot[#1]{\fvar{#2}}}}
\newcommand{\rsample}[2][n]{\ensuremath{\Xdot[#1]{\rvar{#2}}}}
\newcommand{\fvec}[2][n]{\ensuremath{\boldsymbol{\underline{\fvar{#2}}}^{(#1)}}}
\newcommand{\rvec}[2][n]{\ensuremath{\boldsymbol{\underline{\rvar{#2}}}^{(#1)}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% subsets, realizations
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Fn}[1][n]{\ensuremath{F_{#1}}}
\newcommand{\Fnsym}[1][2n]{\ensuremath{F_{#1}^{\text{sym}}}}

\newcommand{\Ft}{\ensuremath{F^{t}}}

\newcommand{\sn}{\ensuremath{\sigma_n}}
\newcommand{\tn}{\ensuremath{\tau_n}}
\newcommand{\stn}{\ensuremath{\sn,\tn}}
%\newcommand{\sn}{\ensuremath{\rvec{X}}}
%\newcommand{\tn}{\ensuremath{\rvec{Y}}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  operators
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\ass}{\ensuremath{:=}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% expected and empirical risk
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Rexp}[1]{\ensuremath{\text{R}[#1]}}
\newcommand{\Remp}[2]{\ensuremath{\text{Remp}[#1,#2] }}
\newcommand{\Rempdiff}[3]{\ensuremath{\text{Remp}[#1,#2]-
    \text{Remp}[#1,#3] }}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Rademacher...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \radsum{f}{X} or \radsum[n]{f}{X}
\newcommand{\radsum}[3][n]{\ensuremath{\frac{1}{#1} 
    |\sum_{i=1}^#1 \epsilon_i {#2} (#3_i )|}}
% \radsumb{f}{X}
\newcommand{\radsumb}[2]{\ensuremath{ 
    |\sum_{i=1}^n \epsilon_i {#1} (#2_i )|}}
% \radvar{F} or \radvar[n]{F}
\newcommand{\radvar}[2][n]{\ensuremath{S_#1(#2)}}
% \radvarsum{F}{X} or \radvarsum[n]{F}{X} 
\newcommand{\radvarsum}[3][n]{\ensuremath{\sup_{#3} E_{\epsilon} \frac{1}{\sqrt{#1}}
    \sup_{g \in #2} | \sum_{i=1}^#1 \epsilon_i  g({#3}_i)|}}
\newcommand{\radvarsumB}[3][n]{\ensuremath{E_{#3} E_{\beta} \frac{1}{\sqrt{#1}}
    \sup_{g \in #2} | \sum_{i=1}^{#1} \beta_i  g({#3}_i)|}}
% \radsumdiff{f}{X}{Y} or \radsumdiff[n]{f}{X}{Y}
\newcommand{\radsumdiff}[4][n]{\ensuremath{\frac{1}{#1}
     \sum_{i=1}^#1 \epsilon_i ( {#2} (#3_i ) -{#2} (#4_i )) }}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% luckiness
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \luckyset{f}{X}
\newcommand{\luckyset}[2]{\ensuremath{H(#1,#2)   }}
% \omegaf{X} or \omegaf{\delta}{X}
\newcommand{\omegaf}[2][\delta]{\ensuremath{\omega\bigl(L(f, #2), n,
    {\textstyle #1}\bigr)}}
% \level{f}{X}
\newcommand{\level}[2]{\ensuremath{l(F(#1,#2)) }}
% \covno{s}{F}{d}
\newcommand{\covno}[3]{\ensuremath{N\bigl({\textstyle #1},#2,#3\bigr)}}
% \packno{s}{F}{d}
\newcommand{\packno}[3]{\ensuremath{\D\bigl({\textstyle #1},#2,#3\bigr)}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% algo luckiness
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\aluckyset}[1]{\ensuremath{G(#1) }}
% \afirstset{Z} or \afirstset[d]{Z}
\newcommand{\afirstset}[2][d^*_{XY}]{\ensuremath{G^{#1}_{\cal A}({#2}) }}
\newcommand{\aomegaf}[2][\frac{\delta}{4}]{\ensuremath{\omega\bigl(L(A,#2),n,#1,\dots\bigr)}}
%\newcommand{\omegafa}[2][\frac{\delta}{4}]{\ensuremath{\omega(L^A_n(A,#2),n,#1,\frac{1}{2n})}}
\newcommand{\omegafa}[2][\delta]{\ensuremath{\omega\bigl(L({\cal A}(#2)),n,#1\bigr)}}
\newcommand{\alevel}[1]{\ensuremath{l(F_A(L,#1)) }}

\newcommand{\aRexp}[1]{\ensuremath{\text{R}[A(#1)]}}
\newcommand{\aRemp}[2]{\ensuremath{\text{Remp}[A(#1),#2]}}
\newcommand{\aRempdiff}[3]{\ensuremath{\text{Remp}[A(#1),#2]
    -\text{Remp}[A(#1),#3] }}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% my luckiness
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \rluckyset{f}{X} or \rluckyset[F]{f}{X}
\newcommand{\rluckyset}[3][F]{\ensuremath{#1(#2,#3) }}
% \romegaf{f}{X} or \romegaf[\delta]{f}{X}
\newcommand{\romegaf}[3][\frac{\delta}{4})]
{\ensuremath{\omega(L(#2, #3),n,#1)}}
% \rlevel{F}{f}{X} or \rlevel[n]{F}{f}{X}
\newcommand{\rlevel}[4][n]{\ensuremath{S_{#1}(#2(#3,#4)) }}
% \myalevel{F}{X} or \myalevel[n]{F}{X}
\newcommand{\myalevel}[3][n]{\ensuremath{S_#1(#2_A(L,#3)) }}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% jmlr
\jmlrheading{5}{2004}{219--238}{12/02}{3/04}{Shahar Mendelson and Petra Philips}
\ShortHeadings{On the Importance of Small Coordinate Projections}{Mendelson
  and Philips}
\firstpageno{219}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}
\title{On the Importance of Small Coordinate Projections  }
% jmlr
\author{\name Shahar Mendelson \email shahar.mendelson@anu.edu.au\\
\name Petra Philips \email petra.philips@anu.edu.au\\
\addr RSISE, The Australian National University \\
Canberra, ACT 0200, Australia} 

\editor{Peter Bartlett}


% springer
%\author{Shahar Mendelson\inst{1} \and Petra Philips\inst{1}}
%\institute{RSISE, The Australian National University, Canberra, ACT
%0200, Australia. \email{shahar.mendelson@anu.edu.au},
%\email{petra.philips@anu.edu.au}}


\maketitle

%\abstract{ 
\begin{abstract}%
It has been recently shown that sharp generalization
  bounds can be obtained when the function class from which the algorithm
  chooses its hypotheses is ``small" in the sense that the  Rademacher averages 
of this function class are small.
We show that a new more general principle guarantees good generalization bounds.
The new principle
  requires that  random coordinate projections 
of the function class evaluated on random samples are ``small" with high
  probability and that the random class of functions allows symmetrization.
%The only additional sufficient ingredient is the capability of symmetrization 
%with respect to the random class of functions. 
As an example, we prove that this geometric
  property of the function class is exactly the reason why the two lately proposed 
frameworks, the {\it luckiness} \citep{luck} and the {\it algorithmic
  luckiness} \citep{algoluck}, can be used to establish generalization  bounds. 
\end{abstract}
%}

\begin{keywords}
Statistical learning theory, generalization bounds, data-dependent
complexities, coordinate projections 
\end{keywords}


\section{Introduction}

Generalization bounds are used to show that, with high
probability, functions produced by a learning algorithm have a
small error, and as such, can be used to approximate the unknown
target. For many years, such bounds were obtained by deviation
estimates of empirical means from the actual mean, {\it uniformly} over
the whole class of functions from which the algorithm produces its
hypothesis. Thus, classes which satisfy the uniform law of large
numbers (so-called uniform Glivenko-Cantelli or GC classes) have
played a central role in Machine Learning literature. 
More recently, other methods of deriving generalization bounds were
developed, in which the ``size" of the function class from  which the
algorithm chooses a hypothesis is not specified {\em a priori}. Examples of such methods
are the {\it luckiness} \citep{luck} and the {\it algorithmic
luckiness} \citep{algoluck} frameworks, but although in  both cases one can obtain
generalization bounds, they  seem to be based on completely
different arguments.

In this article, we show that the bounds obtained in all these frameworks follow from 
the same general principle. This principle requires that coordinate projections of a function 
subclass on random samples are ``small" with high probability.

We consider the following setting for the learning problem: let
 $\Omega$ be  a measurable input space, $ t: \Omega \longrightarrow \R$
an unknown  real-valued target function, $H = \{h \, |\, h: \Omega \longrightarrow \R\}$
a class of hypothesis functions, and $\mu$ an  unknown probability distribution on $\Omega$.
Let $(X_1,...,X_n) \in \Omega^n$ be a finite training sample, 
where each $X_i$ is generated randomly, independently, according to $\mu$. 
Based on  the values of the target function on this sample, $(t(X_1),...,t(X_n))$,
the goal of a learning algorithm is to choose a function $h^* \in H$ which is
a good  estimator of  the target function $t$.
A quantitative measure of how well a function $h \in H$ approximates $t$ is
 given by a loss function $l: \R \times \R \longrightarrow \R$. Typical examples
of loss functions are the 0-1 loss for classification defined by $l(r,s) = 0$ if $r = s$ and $l(r,s) = 1$ if $r
\neq s$ or the square-loss for regression tasks $l(r,s) = (r-s)^2$. 
% add excess loss 
In what follows we will assume
a bounded loss function and therefore, without loss of generality,
$l: \R \times \R \longrightarrow [-1,1]$. For every $h \in H$ we define
the associated loss function $l_h: \Omega \longrightarrow [-1,1]$,
$l_h(x) \ass l(h(x), t(x))$ and denote by $F = \{l_h: \Omega \longrightarrow
[-1,1]\, |\, h \in H \}$ the loss class associated with the learning problem.
If $h^*$ is the best estimate for $t$ in $H$, we call     
$F' = \{l_h - l_{h^*} |\, h \in H \}$ the excess loss class.

The best estimate for t is defined to be the $h^* \in H $ for which 
the expected loss (also called risk) over all possible observations is
as small as possible, that is, $ \int l_{h*}(x) d\mu(x) = \E_\mu l_{h*} \approx {\text{inf}_{h \in
  H}} \ \E_\mu l_h$.
Empirical risk minimization algorithms are based on the philosophy that it is
possible to approximate this expectation with the
empirical mean, and choose instead  a hypothesis $\hat{h} \in H $ for which 
 $\frac{1}{n} \sum_{i=1}^n l_{\hat{h}}(x_i) \approx \text{inf}_{h \in
  H} \ \frac{1}{n} \sum_{i=1}^n l_h(x_i)$.
Therefore, the relationship between expected and empirical loss is of crucial
importance for the performance of these learning algorithms.

In the classical approach to obtain generalization bounds,
called  GC-type bounds, one investigates the
probability that, for {\it any} hypothesis in the class, the deviation 
of  the empirical mean from the actual mean of its associated loss function
is larger than a given threshold, that is,
\begin{equation} \label{eq:GC}
Pr \Bigl\{ \sup_{f \in F} \big| \E_\mu f -\frac{1}{n}\sum_{i=1}^n
f(X_i) \bigr| \geq t \Bigr\},
\end{equation}
where  $\mu$ is a probability measure on $\Omega$, 
$X_1,...,X_n$ are independent random variables distributed
according to $\mu$, 
$F$ is the loss  class associated with the learning problem,
and $\E_\mu f$ denotes $\E f(X_i)$.
%Since F is a class of loss functions we can and will assume that 
%$F$ is a class of real-valued functions defined on a measurable space 
%$\Omega$ which take values in $[-1,1]$.

Classes of functions $F$ which, independently of the underlying
measure $\mu$, satisfy the law of large numbers, that is,
the probability  \eqref{eq:GC} tends to $0$ as $n$ goes to infinity uniformly
in $\mu$,
are called {\it uniform Glivenko-Cantelli classes}. 
For these classes learning is possible. 
Historically, uniform Glivenko-Cantelli classes
were characterized  by a finite combinatorial dimension (e.g., a finite VC
dimension in the {0,1}-case) \citep[see][]{VC,ABCH}.
The ability to bound the
tails of the random variable in \eqref{eq:GC} is therefore due to the fact that the class
$F$ is ``small" in some sense. 

In \citet{Men:GC,Men:smallsets} it has been shown that parameters which also
characterize the uniform Glivenko-Cantelli property are the {\it uniform
  Rademacher averages}  of the class $F$, defined as 
$$
R_n(F) \ass \sup_{\{x_1,...,x_n\} \subset \Omega^n} \E_\eps
\sup_{f \in F} \big| \sum_{i=1}^n \eps_i f(x_i) \big|,
$$
where $(\eps_i)_{i=1}^n$ are independent, symmetric,
$\{-1,1\}$-valued random variables, also known as Rademacher
random variables.
The necessary and sufficient condition for a
 class $F$ to be a uniform Glivenko-Cantelli class is that 
$R_n(F) = o(n).$  %\label{eq:RnGC}$ 
In this case, tail estimates 
for \eqref{eq:GC} which are independent of the underlying measure $\mu$ 
 can be as fast as the order of $e^{-cnt^2}$.
Therefore, the Rademacher averages $R_n(F)$ seem to be a reasonable  
notion of ``size" for a function 
class $F$ in the context of learning via the uniform law of large numbers. 

It was shown in \citet{Men:smallsets} that---if $F$ satisfies mild structural assumptions---it is possible to derive 
sharper bounds  
on the learning problem by bounding
 the  probability 
\begin{equation} \label{eq:learning}
Pr \Bigl\{ \exists {f \in F},\  \frac{1}{n}\sum_{i=1}^n f(X_i)
\leq t, \ \E_\mu f \geq 2t \Bigr\}
\end{equation}
instead of \eqref{eq:GC}.
The difference in the two cases is that in \eqref{eq:GC} one
controls the deviation of the empirical means from the actual one for {\it all} the functions in the class, whereas in \eqref{eq:learning}
the control is only for functions with ``small" empirical mean,
that is, potential minimizers for the actual mean. 
The tail estimates for \eqref{eq:learning} can be as good as  $e^{-cnt}$ instead of $e^{-cnt^2}$
and are governed by the Rademacher averages $R_n(\Ft)$ of  the class
$\Ft \ass \{f \in F : \ \E_\mu f^2 \leq t\}$.

In other words, in both these cases measure independent estimates 
depend on the fact that for {\it all} coordinate projections, 
the projected sets
$\big\{ \big(f(x_1),...,f(x_n)\big): \ f \in F \big\}$ and respectively
$\big\{ \big(f(x_1),...,f(x_n)\big): \ f \in \Ft \big\}$ are small in
the sense that they have small Rademacher averages. Clearly, this is
a property of the class $F$, and if one wishes to obtain useful
bounds, one has to assume {\em a priori} that $F$ is small.


In this article we show that the fact that classes have ``small"
coordinate projections with high probability (for a fixed probability measure)
is the reason that
the tails of \eqref{eq:GC} and \eqref{eq:learning} are well behaved.
More surprising is the fact that this is also the reason why 
several other (seemingly very different) approaches yield generalization
bounds.

The method of analysis we use is a combination of a symmetrization with
respect to a random subclass and sharp concentration results. The need to
investigate random subclasses is simple, as the starting point is that,
ultimately, one wants to  control the generalization ability {\it only} 
for the hypothesis functions which are reachable by the specific learning 
algorithm when presented with the actual training sample.
Therefore, it suffices to obtain estimates on
\begin{equation} \label{eq:subset}
Pr \Bigl\{ \sup_{f \in F'}\big| \E_\mu f -\frac{1}{n}\sum_{i=1}^n
f(X_i) \bigr| \geq t \Bigr\},
\end{equation} 
where $F' \subset F$ and $\hat{f} \in F'$, where $\hat{f}$ is the loss
function associated with the 
hypothesis produced by the algorithm from the
sample $(X_1,  \dots ,X_n)$.
Although one can hope that $F'$ has a smaller ``size" than $F$, it is not possible to use the
  classical uniform generalization bounds  because $F'$ depends on the random
  training sample and could  change with the sample.




The outline of this paper is as follows: in Section~\ref{sec:symmetrization} we will 
first present  a symmetrization procedure which
is performed with respect to a random subclass of functions.
The proof is a modification of the original proof of the standard
symmetrization argument. 
The probability in Equation~\eqref{eq:subset} can be therefore related 
 to the probability of having large Rademacher 
sums for the (random) coordinate projections 
of this random subclass. 
Sharp generalization bounds can be obtained when  the 
``size" of the set of coordinate 
projections of the random subclass is ``small" in the sense that  with high
probability the
Rademacher averages associated with a random projection of a random subclass 
 are small (Corollary \ref{cor:main}). 
We conclude that the general principle which ensures learnability and 
fast error rates  consists of the combination of three main ingredients:
a symmetrization procedure,  a sharp concentration 
inequality, and a small ``size" for the set of random coordinate projections.

In Section~\ref{sec:examples} we show how 
apparently different approaches fall within this general framework.
In Section~\ref{sec:GC} we present the GC case \eqref{eq:GC} as an 
easy corollary of the symmetrization procedure.
It is considerably more difficult
to obtain the sharp rates for \eqref{eq:learning}, a fact which is
demonstrated in Section~\ref{sec:learning}. In both these
examples, the class whose coordinate projections have to be
controlled is not random, but a deterministic subset of $F$. 

There are several examples in which one really requires random subclasses of
$F$. The examples we shall present are of the luckiness and algorithmic luckiness
frameworks.
The reason we chose these examples and not others is because our methods give
considerably shorter proofs that seem to clarify the reason why luckiness and
algorithmic luckiness work to the extent that they do.

In the luckiness and algorithmic luckiness frameworks, it is possible to avoid the 
detour via the worst-case quantity in \eqref{eq:GC}
and to derive  bounds using additional prior knowledge on
the learning algorithm or on the training sample.
The bounds stated in these approaches are, as opposed to the existing 
classical ones, data- or algorithm-dependent.

In the luckiness framework \citep{luck}, prior knowledge about the connection between the
actual sample and the functions in $F$ is quantified through a luckiness function. 
A ``fortunate" property of this luckiness function ($\omega$-smallness) 
ensures good tail estimates for \eqref{eq:subset}. One example for a luckiness 
function is the size of the margin for linear classifiers.

The algorithmic luckiness framework \citep{algoluck} generalizes  
the luckiness framework. Prior knowledge about the link between  the functions
learned by the algorithm and the actual sample are formulated through an algorithmic
luckiness function whose property of ``$\omega$-smallness" enables one to
bound  the generalization error.


Although there are no examples in which  these methods yield results
clearly better than other approaches, one  merit of these two frameworks is 
that they set up a possible theoretical basis that could enable one to
directly estimate data-dependent and algorithm-dependent generalization
bounds. Unfortunately, the ``$\omega$-smallness" property is somewhat 
technically complicated and seems unnatural. The notion of
complexity for the function class employed in these frameworks is  covering numbers,
 and it was unexplored how these frameworks link to approaches using
 Rademacher averages as a notion of size.


We show that the
$\omega$-smallness condition is just a way of ensuring that a
random coordinate projection of the random set is ``small" and
this suffices to recover the original generalization bounds.
Hence, both luckiness and algorithmic luckiness fall within the
general framework.

Note also that other examples of generalization bounds for data-dependent
hypothesis classes
that could be obtained using our methods are presented in \citet{Gat99} and \citet{CanEtt02}. 
In fact, the proofs in \citet{Gat99} and \citet{CanEtt02} are based on a similar 
symmetrization argument. The notion of ``size" which is employed 
 is simply that of 
cardinality, and thus these results  easily fall within the framework
presented here \citep[for details see][]{MenPhi03}.

We end this introduction with some notation which will be used throughout the article. 
In the following,  $F$ is a  class of real-valued functions defined on a
measurable space $\Omega$ which take values in $[-1,1]$ and 
$\mu$ is a probability measure on $\Omega$. $\Omega^n$ denotes the product space
 $\Omega \times \dots \times \Omega$. Let $X_1,...,X_n$
be independent random variables distributed according to $\mu$ and let
 $(Y_1,...,Y_n)$ be an independent copy of $(X_1,...,X_n)$. 
$\mu_n$ denotes the random
empirical probability measure supported on $\{X_1,...,X_n\}$, that is,
 $\mu_n \ass n^{-1}\sum_{i=1}^n \delta_{X_i}$. $Pr_\mu$ and $\E_\mu$ are the
 probability and the expectation with respect to 
 $\mu$ and  $Pr_\X$ and $\E_\X$  denote the
 probability and the expectation with respect to the random vector  $\X=(X_1,
 \dots, X_n)$ (and therefore with respect to $\mu^n$). $\E_\mu f$ is the
 expectation  and ${\rm var}(f)$ is the
 variance of the random variable $f(X_i)$. In general, for
 any 
random variable $Z$, $Pr_Z$ and $\E_Z$  are the
 probability and the expectation with respect to the distribution of $Z$.
 
Let $F/\X$ be the random set $\{(f(X_1),...,f(X_n)\big) :\, f \in F\}$, that is, 
the coordinate projection of the set $F$ onto the random set of coordinates $\X$.
$VC(F)$ is the VC-dimension of $F$ if $F$ is a boolean class of functions.


Set $\ell_p^n$ to be $\R^n$ with the norm
$\|x\|_p \ass \bigl(\sum_{i=1}^n |x_i|^p \bigr)^{1/p}$ and put $B_p^n$
to be the unit ball of $\ell_p^n$. $\ell_\infty^n$ is $\R^n$
endowed with the norm $\|x\|_\infty \ass \sup_{1 \leq i \leq n} |x_i|$,
let $L_\infty(\Omega)$ be the set of bounded functions on
$\Omega$ with respect to the norm $\|f\|_\infty \ass \sup_{\om \in
\Omega} |f(\omega)|$, and denote its unit ball by  $\bi$. For a
probability measure $\mu$ on a measurable space $\Omega$ and $1
\leq p <\infty$, let $L_p(\mu)$ be the space of measurable
functions on $\Omega$ with a finite norm $\|f\|_{L_p(\mu)} \ass (\int
|f|^p d\mu)^{1/p}$. 
%The Lipschitz norm of a function $f$ on a metric space
%$(T,d)$ taking values in a normed space $(S, \| \cdot \|)$ is defined  by 
%$$\|f\|_{lip} =
%\sup \Bigl\{\frac{\|f(s)-f(t)\|}{d(s,t)}: s,t\in T, s\not= t  \Bigr\}.$$ 
 

Let $(Y,d)$ be a metric space. If $F \subset Y$ then for every
$\eps>0$, $N(\eps,F,d)$ is the minimal number of open balls (with
respect to the metric $d$) needed to cover $F$. A corresponding set
$\{y_1,...,y_m\} \subset Y$ of minimal cardinality  such that for every 
$f \in F$ there is some $y_i$ with $d(f,y_i) < \eps$ 
is called an $\eps$-cover of $F$.  For $1 \leq p <\infty$, denote by
$N\bigl(\eps,F,L_p(\mu_n)\bigr)$ the covering number of $F$ at
scale $\eps$ with respect to the $L_p(\mu_n)$ norm. Similarly, one
can define the packing number at scale $\eps$, which is the maximal
cardinality of a set $\{y_1,...,y_k\} \subset F$ such that for
every $i \not = j$, $d(y_i,y_j) \geq \eps$. Denote the
$\eps$-packing numbers by $\D(\eps,F,d)$ and note that for every
$\eps>0$, $N(\eps,F,d) \leq \D(\eps,F,d) \leq N(\eps/2,F,d)$.
If $S$ is a set, we denote its complement by $S^c$.

Finally, throughout this article all absolute constants are
denoted by $c$, $C$ or $K$. Their values may change from line to
line, or even within the same line. 


\section{Symmetrization} \label{sec:symmetrization}
%Let $F$ be a class of real-valued functions defined on a
%measurable space $\Omega$ which take values in $[-1,1]$, and set
%$\mu$ to be a probability measure on $\Omega$. Let $X_1,...,X_n$
%be independent random variables distributed according to $\mu$ and
%put $\{Y_1,...,Y_n\}$ to be an independent copy of
%$\{X_1,...,X_n\}$. Recall that $\mu_n$ denotes the random
%empirical probability measure supported on $\{X_1,...,X_n\}$.

For every integer $n$, let $\Fn$ and \Fnsym[n] be set-valued
functions which assign to each $\sn \in \Omega^n$ a subset of $F$.
We assume that \Fnsym[n] is invariant to permutations, that is, for
every $ \sn \in \Omega^n$ and every permutation $\pi(\sn)$ of $\sn$, $\Fnsym[n](\sn)
= \Fnsym[n](\pi(\sn))$, in which case we say that \Fnsym[n] is symmetric.

The question we wish to address in this section is how to estimate the
probability 
\begin{equation} \label{eq:subsetrand}
Pr_\X\Bigl\{ \sup_{f \in \Fn(\sn)}\big| \E_\mu f -\frac{1}{n}\sum_{i=1}^n
f(X_i) \bigr| \geq t \Bigr\},
\end{equation} 
where $\sn=(X_1,...,X_n)$ is a random sample.
Note that the worst-case probability \eqref{eq:GC} 
is a special case of \eqref{eq:subsetrand}, where  $\Fn$ is
the constant function mapping every sample to the whole function class $F$, 
$\Fn(\sn) = F$. Another extreme case occurs when $\Fn(\sn)= \{\hat{f}\}$,
where $\hat{f}$ is the loss function associated with the  
hypothesis produced by a learning algorithm from the
sample $\sn$.

We will show that by employing an additional assumption on the functions
$\Fn$ and $\Fnsym[n]$  which relates the
random subsets $\Fn(\sn)$ 
to {\it symmetric} random subsets dependent on a
double-sample, it is possible to upper bound \eqref{eq:subsetrand}
in terms of Rademacher sums associated with sets of coordinate
projections.  

\begin{Assumption} \label{ass}
There exists a constant $\delta>0$ such that for every $t>0$,
\begin{align}
Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fn(\sn), \
\Bigl|\frac{1}{n}\sum_{i=1}^n \bigl(f(X_i)-f(Y_i)\bigr)\Bigr| \geq
t \Bigr\} \nonumber
\leq \\
Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fnsym(\stn), \
\Bigl|\frac{1}{n}\sum_{i=1}^n \bigl(f(X_i)-f(Y_i)\bigr)\Bigr| \geq
t \Bigr\} + \delta, \label{eqRS:stab2}
\end{align}
where $\sn=(X_1,...,X_n)$ and $\tn=(Y_1,...,Y_n)$.
\end{Assumption}

This assumption  quantifies that  
by replacing the original random 
subset of hypotheses  with another symmetric random subset dependent on 
the double-sample---and which is therefore invariant under permutations of
this double-sample---the probability  of having large
deviations of empirical means evaluated on the sample and ghost sample increases by
at most  $\delta$ and therefore not ``too much".

Indeed, in all the applications we present $\delta$ can be made as small
as we require. One extreme case occurs when for every
double-sample $(\stn)$,
\begin{equation*} %\label{eqRS:stab1}
\Fn(\sn) \subseteq \Fnsym(\stn),
\end{equation*}
in which case Assumption \ref{ass} holds trivially with a constant
$\delta=0$. For example, if  both set-valued maps are 
the constant function $\Fn(\sn) =\Fnsym[n](\sn) = F$, then $\delta=0$. 

Given $\Fn$, one can always define a mapping  $\Fnsym$ to satisfy Assumption \ref{ass}
as the symmetric 
extension of $\Fn$:  for every double-sample $(\stn)$,
$\Fnsym (\stn)$ is defined to be  the union of all subsets corresponding to
the first half of
permutations of the  double-sample $(\stn)$,
\begin{equation}
\Fnsym(\stn) \ass \bigcup_{\pi \in S_{2n}} \Fn \bigl(\pi(\stn)|_{i=1}^n
\bigr),\label{eq:Fnsymmax}
\end{equation}
where $S_{2n}$ is the set of permutations on $(1,\dots,2n)$, and
$\pi(\stn)|_{i=1}^n$ is the first half of the permuted double-sample.
However, Assumption \ref{ass} allows us to   
replace the original subset $\Fn(\sn)$ even with a potentially  ``smaller"
symmetric subset $\Fnsym(\stn)$ as long as the change in probabilities can be
controlled.

The importance of  Assumption \ref{ass} lies in the fact that it enables one
to bound the probability \eqref{eq:subsetrand} by 
proving a similar symmetrization argument to that employed in the original proof 
of the uniform Glivenko-Cantelli property. 

The following symmetrization  theorem is the main result of this section.

\begin{Theorem} \label{thm:main}
If Assumption \ref{ass} holds then for every $t>0$,
\begin{multline}
\Bigl(1-\frac{4}{nt^2} \sup_{f \in F}{\rm var}(f) \Bigr) \cdot
Pr_\X \Bigl\{ \exists f \in \Fn(\sn), \ \Big|\E_\mu f
-\frac{1}{n}\sum_{i=1}^n f(X_i) \Big| \geq t \Bigr\} \\ \leq 2
Pr_{\X \times \Y} Pr_{\eps}  \Bigl\{ \exists f \in
\Fnsym(\stn), \ \ \Big|\sum_{i=1}^n \eps_i f(X_i) \Big|
\geq \frac{nt}{4} \Big\} + \delta, \label{eqRS:randomsymmcond}
\end{multline}

where $\sn=(X_1,...,X_n)$ and $\tn=(Y_1,...,Y_n)$.
\end{Theorem}

As the examples we present in the next section show, most of the
standard methods used in Learning Theory fall within the general
framework of Theorem \ref{thm:main}. The advantage of Theorem
\ref{thm:main} is that it reduces the analysis to a geometric
problem, namely, estimating the Rademacher sums associated
with the coordinate projection onto $\sn=(X_1,...,X_n)$ of the
random class $\Fnsym(\stn)$,
$$\Fnsym(\stn)/\sn \ass \Bigl\{\big(f(X_1),...,f(X_n)\big) : \ f
\in \Fnsym(\stn) \Bigr\}. $$

The proof is done in two steps which are the same as in the
standard symmetrization procedure:
a symmetrization by a ghost sample which relates the deviation of the  mean from the
empirical mean  to the deviation of the
empirical means evaluated on two different samples;
and a symmetrization by signs which relates the latter deviation to
   the probability of having ``large" Rademacher sums $\sup_{f \in
     \Fnsym(\stn)} |\sum_{i=1}^n \eps_i f(X_i)|$. 
We present the proof for the sake of completeness.

\begin{Lemma}[Symmetrization by a Ghost Sample] \label{lemma:symmetry}
For every $t>0$,
\begin{align*}
\Bigl(1-\frac{4n}{t^2} \sup_{f \in F}{\rm var}(f) \Bigr) & Pr_\X
\Bigl\{ \exists f \in \Fn(\sn), \ \Bigl|\sum_{i=1}^n
\bigl(f(X_i)-\E_\mu f \bigr)\Bigr| \geq t \Bigr\}
\\ \leq & Pr_{\X \times \Y} \Bigl\{\exists f \in \Fn(\sn), \ \Bigl|\sum_{i=1}^n
\bigl(f(X_i)-f(Y_i)\bigr)\Bigr| \geq  \frac{t}{2} \Bigr\}.
\end{align*}
\end{Lemma}

\proof Define the random processes $Z_i(f)=f(X_i)-\E_\mu f$ and
$W_i(f)=f(Y_i)-\E_\mu f$, and fix $t>0$. Let $\sn=(X_1,...,X_n)$,
put $\beta=\inf_{f \in F} Pr\{|\sum_{i=1}^n Z_i(f)| \leq t/2\}$
and set $A=\{\sn: \ \exists f \in \Fn(\sn), \ |\sum_{i=1}^n Z_i(f) | \geq
t\}$. For every element in $A$ there is some $f \in \Fn(\sn)$ and a
realization
of $Z_i$ such
that $|\sum_{i=1}^n Z_i(f) | \geq t$. Fix this realization and $f$
and observe that by the triangle inequality, if $|\sum_{i=1}^n
W_i(f)| \leq t/2$ then $\big|\sum_{i=1}^n \big(Z_i(f)-
W_i(f)\big)\big| \geq t/2$. Since $(W_i)_{i=1}^n$ is an independent copy of
$(Z_i)_{i=1}^n$,
\begin{align*}
\beta & \leq Pr_{\Y} \Bigl\{ \Bigl|\sum_{i=1}^n W_i(f)\Bigr| \leq
\frac{t}{2}\Bigr\} \leq Pr_\Y\Bigl\{ \Bigl|\sum_{i=1}^n
W_i(f)-\sum_{i=1}^n Z_i(f)\Bigr| \geq \frac{t}{2}\Bigr\} \\
& \leq Pr_\Y\Bigl\{\exists f \in \Fn(\sn), \ \Bigl|\sum_{i=1}^n
W_i(f)-\sum_{i=1}^n Z_i(f)\Bigr| \geq \frac{t}{2}\Bigr\}.
\end{align*}
Since the two extreme sides of this inequality are independent of
the specific selection of $f$, this inequality holds on the set
$A$. Integrating with respect to $\X$ on $A$ it follows that
\begin{align*}
\beta & Pr_\X \Bigl\{ \exists f \in \Fn(\sn), \ \Bigl|\sum_{i=1}^n
Z_i(f)\Bigr| \geq t \Bigr\} \\ \leq & Pr_\X Pr_\Y \Bigl\{ \exists f
\in \Fn(\sn), \ \Bigl|\sum_{i=1}^n \bigl(W_i(f)
-Z_i(f)\bigr)\Bigr| \geq \frac{t}{2} \Bigr\}.
\end{align*}
Finally, to estimate $\beta$, note that by Chebyshev's inequality
\begin{equation*}
Pr \Bigl\{ \Bigl|\sum_{i=1}^n Z_i(f)\Bigr| \geq \frac{t}{2}
\Bigr\} \leq \frac{4n}{t^2}{\rm var}(f)
\end{equation*}
for every $f \in F$, and thus, $\beta \geq 1-(4n/t^2)\sup_{f \in
F}{\rm var}(f)$.
\endproof

\begin{Proposition}[Symmetrization by Random Signs] \label{prop:symm-by-signs}
Let \Fnsym be a symmetric map. Then, for any probability
measure $\mu$ and every $t > 0$,

\begin{align*}
Pr_{\X \times \Y} & \Bigl\{ \exists f \in \Fnsym(\stn), \
\Bigl|\frac{1}{n} \sum_{i=1}^n \bigl(f(X_i)-f(Y_i)\bigr) \Bigr|
\geq t \Bigr\}
\\ & \leq 2Pr_{\X \times \Y}Pr_{\eps} \Bigl\{ \exists f \in \Fnsym(\stn), \
\Big| \sum_{i=1}^n \eps_i f(X_i) \Big| \geq \frac{nt}{2} \Bigr\},
\end{align*}
where $\sn=(X_1,...,X_n)$, $\tn=(Y_1,...,Y_n)$, and
$(\eps_i)_{i=1}^n$ are independent Rademacher variables.
\end{Proposition}

\proof By the symmetry of \Fnsym it follows that for every
$\{\eps_1,...,\eps_
n\} \in \{-1,1\}^n$,
\begin{align*}
Pr_{\X \times \Y} & \Bigl\{ \exists f \in \Fnsym(\stn), \
\Bigl|\frac{1}{n} \sum_{i=1}^n \bigl(f(X_i)-f(Y_i)\bigr) \Bigr|
\geq t \Bigr\}
\\
&=Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fnsym(\stn), \
\Bigl|\frac{1}{n} \sum_{i=1}^n \eps_i\bigl(f(X_i)-f(Y_i)\bigr)
\Bigr| \geq t \Bigr\}.
\end{align*}
Taking the expectation with respect to the random signs (that is,
with respect to the Rademacher random variables), the proof
follows from the triangle inequality and the fact that
$(X_1,...,X_n)$ has the same distribution as $(Y_1,...,Y_n)$.
\endproof

\noindent {\bf Proof of Theorem \ref{thm:main}.} The claim follows
immediately by combining Lemma \ref{lemma:symmetry}, Assumption
\ref{ass} and Proposition \ref{prop:symm-by-signs}.
\endproof

We can now relate the Rademacher sums from  Theorem \ref{thm:main}  
to the Rademacher averages of  $\Fnsym(\stn)/\sn$
 by employing  concentration inequalities for the random variable
$$Z = \sup_{f \in \Fnsym(\stn)} \big|
\sum_{i=1}^n \eps_i f(X_i) \big| = \sup_{v \in \Fnsym(\stn)/\sn} \big|
\sum_{i=1}^n \eps_i v_i \big|$$ around its conditional mean $\E_\eps (Z |
X_1,...,X_n, Y_1,...,Y_n)$.

For example, we state one particular concentration result  which follows directly from 
martingale methods \citep[see, e.g.,][]{McDia89} for functions with bounded differences:
\begin{Theorem}[Concentration]
For
every set $V \subset B_\infty^n$ and every $t>0$,
\begin{equation} \label{eq:MP}
Pr_{\eps} \Bigl\{ \sup_{v \in V} \Big| \sum_{i=1}^n \eps_i v_i
\Big| - \E_{\eps} \sup_{v \in V}  \Big| \sum_{i=1}^n \eps_i v_i
\Big| > t \Big\} \leq e^{-\frac{t^2}{2n}}.
\end{equation}
\end{Theorem}
\proof
Define $h(\eps_1,
\dots,\eps_n) \ass \sup_{v \in V} \Big| \sum_{i=1}^n \eps_i v_i\Big|$.
By the triangle inequality, for every $1 \leq i \leq n$, 
$$  \sup_{\{\eps_1, \dots ,\eps_n,
  \tilde{\eps_i}\}}|h(\eps_1, \dots, \eps_n) - h(\eps_1, \dots ,\eps_{i-1},
  \tilde{\eps_i}, \eps_{i+1}, \dots, \eps_n)| \leq 2,$$
and the claim follows directly from McDiarmid's inequality for $h$.
\endproof
In particular, setting $V$ to be the (random) coordinate projection of 
$\Fnsym(\stn)$ onto $\sn$, 
$$
V \ass \Fnsym(\stn)/\sn=\Bigl\{\big(f(X_1),...,f(X_n)\big) : \ f
\in \Fnsym(\stn) \Bigr\}
$$
and $A_t$ to be the set of double-samples $(\stn)$ with small Rademacher averages for
the projections onto $\sn$, 
$$A_t \ass \big\{(\stn) \ : \ \E_\eps \sup_{v \in V}
\big|\sum_{i=1}^n \eps_i v_i \big| \leq nt/8 \big\},$$
it follows by the union
bound and Equation~\eqref{eq:MP}
that
\begin{align*}
Pr_{\X \times \Y} Pr_{\eps}& \Bigl\{ \exists f \in
\Fnsym(\stn),  \ \Big|\sum_{i=1}^n \eps_i f(X_i) \Big|
> \frac{nt}{4} \Big\} \\ & \leq Pr_{\X \times \Y} \{A^c_t\}
+e^{-\frac{nt^2}{128}}.
\end{align*}

\begin{Corollary} \label{cor:main}
If Assumption \ref{ass} holds, then for every $t>0$
\begin{align*}
\Bigl(1-\frac{4}{nt^2} \sup_{f \in F}{\rm var}(f) \Bigr)& \cdot
Pr_\X \Bigl\{ \exists f \in \Fn(\sn), \ \Big|\E_\mu f
-\frac{1}{n}\sum_{i=1}^n f(X_i) \Big| \geq t \Bigr\} \\
& \leq 2\bigl(Pr_{\X \times \Y}\{A^c_t\}+e^{-\frac{nt^2}{128}}\bigr)
+\delta,
\end{align*}
where $V \ass \Fnsym (\stn)/\sn$ and $A_t \ass \big\{(\stn)\ : \
\E_\eps \sup_{v \in V} \big|\sum_{i=1}^n \eps_i v_i \big| \leq
nt/8 \big\}$.
\end{Corollary}

This corollary illustrates how  Assumption \ref{ass} is sufficient to
guarantee a  generalization  bound with tails of order $e^{-cnt^2}$ for a learning algorithm 
drawing its hypotheses from the random set $\Fn(\sn)$,
as soon as the Rademacher averages of the projection of $\Fnsym(\stn)$ onto
$\sn$ are ``small" with high probability. 

\section{Examples} \label{sec:examples}

In the previous section we have proved that, under the Assumption \ref{ass},
a small ``size" for the set of random coordinate projections 
together with a sharp concentration inequality allow us to derive 
tail estimates for random subsets $\Fn$.
In particular, in order to obtain  tail estimates of the order of
$e^{-cnt^2}$, by Corollary \ref{cor:main}, it is  sufficient to find symmetric random subsets $\Fnsym(\stn)$
which satisfy   Assumption  \ref{ass} and for which the probability
 $$
Pr_{X \times Y} \Bigl\{\E_\eps \Bigl( \sup_{f \in  \Fnsym(\stn)}
|\sum_{i=1}^n \eps_i f(X_i) |\Big| X_1,...,X_n, Y_1,...,Y_n \Bigr)   > \frac{nt}{8} \Bigr\},
$$
is small. 
Now we are ready to show how
apparently different approaches  fall within the framework of Theorem
\ref{thm:main}.

Indeed, we will show that the tail
estimate on \eqref{eq:GC}  and the
generalization bounds in the luckiness and the algorithmic
luckiness frameworks can be derived directly from Corollary \ref{cor:main}.
We will illustrate this by specifying the corresponding  maps $\Fn$ and
$\Fnsym$, and showing that  
for every fixed double-sample $(\stn)$,
$$\E_\eps
\sup_{f \in \Fnsym(\stn)} \big| \sum_{i=1}^n \eps_i f(x_i) \big|,$$
are sufficiently small (of the order $o(n)$).

As we present below, to recover the better estimates for \eqref{eq:learning}
as in \citet{Men:smallsets} is more
delicate because it requires a sharper concentration result than
\eqref{eq:MP}. We will show that these estimates as well follow from 
Theorem \ref{thm:main}, by proving a different concentration inequality which
will enable us to obtain the desired rates of the order of $e^{-cnt}$.

\subsection{Glivenko-Cantelli Classes} \label{sec:GC}

In this section we will demonstrate how one can recover the optimal
deviation estimates for uniform Glivenko-Cantelli classes 
directly from Corollary \ref{cor:main}.


$F$ is called a {\it uniform Glivenko-Cantelli class (GC class)} if for every
$t>0$ 
$$\lim_{n \rightarrow \infty} \sup_\mu Pr \Bigl\{ \sup_{f \in F} \big| \E_\mu f -\frac{1}{n}\sum_{i=1}^n
f(X_i) \bigr| \geq t \Bigr\} = 0. $$

If $F$ is a uniform GC class, by selecting the constant functions 
$$\Fn(\sn)= F, \ \ \Fnsym[n](\sn) = F,$$ Assumption \ref{ass} is  trivially
satisfied with $\delta=0$ and
$$
\Fnsym(\stn)/\sn = \Bigl\{\big(f(X_1),...,f(X_n)\big) : \  f
\in F\Big\}
$$
for every double-sample $(\stn)$. The fact that these
coordinate projections are ``small" follows from the
characterization of uniform GC classes, an observation we shall
return to later.
\begin{Theorem} \label{thm:GC} \citep{Men:GC}
A class of uniformly bounded functions is a uniform GC class if
and only if
\begin{equation*}
\lim_{n \to \infty} \sup_{\{x_1,...,x_n\} \subset \Omega^n}
\frac{1}{n}\E_\eps \sup_{f \in F} \big| \sum_{i=1}^n \eps_i f(x_i)
\big|=0.
\end{equation*}
\end{Theorem}
Recall that
$$
R_n(F)=\sup_{\{x_1,...,x_n\} \subset \Omega^n} \E_\eps
\sup_{f \in F} \big| \sum_{i=1}^n \eps_i f(x_i) \big|
$$
and note that Theorem \ref{thm:GC} ensures that the bound obtained
from Theorem \ref{thm:main} is nonempty. 

In particular, for every
$t>0$ let $n_0$ be such that for every $n \geq n_0$, $R_n(F) \leq
nt/8$. Since $F \subset \bi$ then $\sup_{f \in F}{\rm var}(f) \leq
1$, and thus $1-4\sup_{f \in F}{\rm var}(f)/nt^2 \geq 1/2$,
provided that $n \geq 8/t^2$. Thus, by Corollary \ref{cor:main}
and selecting $N=\max\{8/t^2,n_0\}$ it follows that for every
integer $n>N$ and for any probability measure $\mu$,
\begin{equation*}
Pr \Bigl\{ \sup_{f \in F} \Big|\E_\mu f -\frac{1}{n}\sum_{i=1}^n
f(X_i) \Big| \geq t \Bigr\} \leq 8e^{-\frac{nt^2}{128}}\;.
\end{equation*}
In cases where one has {\em a priori} estimates on the size of the class
(e.g., the shattering dimension or the uniform
entropy), one can recover the optimal GC deviation results. For
example, if $VC(F)=d$, then $R_n(F) \leq C\sqrt{dn}$ where $C$ is
an absolute constant, implying that one can take $n_0=Cd/t^2$, and
thus, for every $n \geq Ct^{-2}\max\{d,\log(1/\delta)\}$,
\begin{equation*}
Pr \Bigl\{ \sup_{f \in F} \Big|\E_\mu f -\frac{1}{n}\sum_{i=1}^n
f(X_i) \Big| \geq t \Bigr\} \leq \delta.
\end{equation*}
Similar estimates can be recovered for classes with a polynomial
shattering dimension by applying the bounds on $R_n(F)$ from
\citet{Men:GC}.

\subsection{Learning Sample Complexity and Error Bounds} \label{sec:learning}

The learning sample complexity is governed by the probability that the
empirical risk minimization algorithm fails, that is, it is the
probability that an empirical minimizer of the loss functional (or
more generally, an ``almost empirical minimizer") will have a
relatively large expectation. Formally, our aim is to estimate
\begin{equation} \label{eq:learning1}
Pr \Bigl\{ \exists f \in F, \ \frac{1}{n}\sum_{i=1}^n f(X_i) \leq
t, \ \E_\mu f \geq 2t \Bigr\},
\end{equation}
where $F$ is the excess squared-loss class. 

The required tail estimates
follow from two principles: The first is a mild structural
assumption on $F$, namely that $F$ is star-shaped around $0$ (i.e.,
for every $f \in F$ and $0 \leq t \leq 1$, $tf \in F$); the second  is that
there is some $B>0$ such that for every $f \in F$, $\E_\mu f^2
\leq B\E_\mu f$. 
Note that there are many examples of loss classes for which this second assumption
could be verified. For example, for nonnegative bounded loss functions, the
associated loss function classes satisfy this property. For convex
classes of functions bounded by 1, the associated excess squared-loss class 
satisfies this property as well, a result that was first shown in \citet{LBW} and 
improved and extended in \citet{BJA} and \citet{Men:smallsets}.


Under these two assumptions, one can show \citep{Men:smallsets} that
 for every $t>0$,
\begin{align} \label{eq:var}
& Pr \Bigl\{ \exists f \in F, \ \frac{1}{n}\sum_{i=1}^n f(X_i)
\leq t, \ \E_\mu f \geq 2t \Bigr\} \nonumber \\
\leq 2& Pr \Bigl\{ \sup_{f \in F, \ \E_\mu f^2 \leq  Bt} \Big|
\E_\mu f -\frac{1}{n}\sum_{i=1}^n f(X_i) \Bigr| \geq t \Bigr\}.
\end{align}
For the sake of simplicity we present our results for $B=1$, which
is the case if $F$ consists of nonnegative functions. The general
case follows an identical path.

It is possible to obtain sharper deviation estimates for \eqref{eq:var}---of the order of $e^{-cnt}$ instead of $e^{-cnt^2}$ like in the uniform GC case---as long as the largest variance of a class member is of
the same order of magnitude as the required deviation. This
follows directly from Talagrand's inequality 
\citep[see][]{Men:smallsets,BBM2}, and was the basis for the estimates on
\eqref{eq:learning1} in \citet{Men:smallsets}. Unfortunately, the
method of proof used in \citet{Men:smallsets} cannot be used
directly in a way which fits our general principle. 
We thus present a different proof which uses the fact
that ``most" coordinate projections of $\{f \in F : \ \E_\mu f^2
\leq t\}$ are contained in a ``small" Euclidean ball. Although the
proof is slightly more complicated than the original one, the
significance of having ``small" coordinate projections is better
exhibited.

Theorem \ref{thm:learning} below is the main result of this
section.
\begin{Theorem} \label{thm:learning}
There are absolute constants $K$, $c$ and $c_1$ for which the
following holds. Let $F \subset \bi$ be star-shaped around $0$
such that for every $f \in F$, $\E_\mu f^2 \leq \E_\mu f$. If 
$t \geq c_1/n$  satisfies that
\begin{equation} \label{eq:condition}
\E \sup_{f \in F, \ \E_\mu f^2 \leq t}
\Big|\sum_{i=1}^n \eps_i f(X_i) \Big| \leq \frac{nt}{16},
\end{equation}
then
\begin{equation*}
Pr \Big\{ \exists f \in F, \ \frac{1}{n}\sum_{i=1}^n f(X_i) \leq
t, \ \E_\mu f \geq 2t\Bigr\} \leq Ke^{-cnt}.
\end{equation*}
\end{Theorem}
For example, if $t_0$ is the minimal $t$ which satisfies
\eqref{eq:condition}, $F$ is a loss class in a proper learning
scenario, and $f^*$ denotes the loss function associated with the
empirical minimizer, then with probability larger than
$1-Ke^{-cnt_0}$,
\begin{equation*}
\E_\mu f^* \leq 2t_0.
\end{equation*}
Note that it is possible to estimate $t_0$, either via {\em a priori}
assumptions on the function class, such as assumptions on the
shattering dimension or the uniform entropy as in
\citet{Men:smallsets}, or from the sampled data as in \citet{BBM2}. For
example, one can show \citep{Men:smallsets,BBM2} that if $F$ is the
star-shaped hull of a Boolean class $G$ and $0$, and if $VC(G)=d$,
then $t_0 =O\bigl(\frac{d}{n}\log\bigl(\frac{en}{d}\bigr)\bigr)$.
Hence, there are absolute constants $c$ and $C$ such that with
probability larger that $1-c(d/n)^d$,
% Shahar?: $1-c(d/n)^{dc'}$   ???????
$$
\E_\mu f^* \leq C\frac{d}{n}\log \Bigl(\frac{en}{d}\Bigr).
$$
The rest of this section will be devoted to the proof of Theorem
\ref{thm:learning}.

First, let us denote the subset of functions in $F$ with variance bounded by t by
$$\Ft \ass \{f \in F, \ \E_\mu f^2 \leq t \}.$$

From \eqref{eq:var} it follows that by setting $\Fn=\Fnsym \ass \Ft$, 
and applying Theorem \ref{thm:main} (Assumption \ref{ass} holds
trivially with $\delta=0$), the probability we want to estimate 
is bounded by the probability $Pr_{\X \times \Y}Pr_\eps \Bigl\{\exists f \in \Ft, \
\Bigl|\sum_{i=1}^n \eps_i f(X_i) \Bigr| \geq \frac{nt}{4} \Bigr\}$.

We will show that the condition \eqref{eq:condition} is just a way of ensuring
that, with high probability, the coordinate projections of $F^t$ onto a random
sample are small. This, together with a sharp concentration result will yield
the desired result.

Let
$$
Z_t(X_1,...,X_n) \ass \E_\eps \sup_{f \in \Ft} \big| \sum_{i=1}^n
\eps_i f(X_i) \big|.
$$
The first step in the proof is based on an inequality due to
Boucheron, Lugosi, and Massart which will allow us to bound the
probability that $Z_t$ deviates from its expectation.
\begin{Theorem} \label{BLM2} \citep{BLM2}
Let $V_1,...,V_n$ be independent, identically distributed random
variables which take values in a Banach space $B$, and assume that
$\|V_i\| \leq 1$ almost surely. Set 
$$Z \ass \E \big(\|\sum_{i=1}^n
\eps_i V_i \| \ \big| \ V_1,...,V_n \big).$$
 Then, for any $t>0$,
\begin{equation*}
Pr \bigl(Z \geq \E Z +t \big) \leq e^{-\frac{t^2}{2\E Z +2t/3}}.
\end{equation*}
\end{Theorem}

To apply this theorem to $Z=Z_t$, let $B=\ell_\infty(F)$, which is the set of
all bounded functions $z:F \to \R$ such that
$\|z\|_{\ell_\infty(F)}=\sup_{f \in F} |z(f)|$. Let $V_i \ass X_i$ and
define $X_i(f) \ass f(X_i)$. Hence, $\|X_i\|_B \leq 1$ and
$\|\sum_{i=1}^n \eps_iV_i \|_B=\sup_{f \in F} |\sum_{i=1}^n \eps_i
f(X_i)|$.
 
If $t$ is such that $\E Z_{t} \leq nt/16$ then by Theorem
\ref{BLM2},
\begin{equation} \label{eq:1}
Pr_\X \Bigl\{ \E_\eps \sup_{f \in \Ft}\Big|\sum_{i=1}^n \eps_i f(X_i)
\Big| > \frac{nt}{8} \Bigr\} \leq e^{-cnt},
\end{equation}
where $c$ is an absolute constant. Hence, with
$\Fnsym(\stn) = \Ft$ and
$$A_t = \{(\stn) : \ \E_\eps \sup_{f
\in \Ft} |\sum_{i=1}^n \eps_i f(X_i)| \leq nt/8\},$$ where
$\sn=(X_1,...,X_n)$ and $\tn=(Y_1,...,Y_n)$ as before,
it follows that
\begin{equation*} %\label{eq:2}
Pr_{\X \times \Y}\{A^c_t\} \leq e^{-cnt}.
\end{equation*}

For a fixed $(\stn) \in A$, we require a sharp concentration result
for
$$
W_t(\eps_1,...,\eps_n) \ass \sup_{f \in \Ft} |\sum_{i=1}^n \eps_i
f(X_i)|,
$$
since  \eqref{eq:MP} leads only to a tail estimate
of $e^{-cnt^2}$. To that end, we use Talagrand's convex-distance
inequality \citep{Tal-conv} (let us mention that our estimates also
follow from an earlier result due to 
\citealt{John-Sch}). We will formulate the concentration result only in the context we
require \citep[see][pg. 76]{Ledoux}.
\begin{Theorem} \label{thm:conc-rad}
Let $T \subset \ell_2^n$ and set $\sigma \ass \sup_{t \in T}
\|t\|_{\ell_2^n}$. Define the random variable $G \ass \sup_{t \in
T} |\sum_{i=1}^n \eps_i t_i|$, and denote its median by $M_G$.
Then for every $r>0$,
\begin{equation*}
Pr \bigl\{ |G-M_G|>r \bigr\} \leq 4e^{-r^2/4\sigma^2},
\end{equation*}
and $|\E G - M_G| \leq 4\pi \sigma$.
\end{Theorem}

In our case, $T$ is the image of $F$ under the coordinate
projection onto the random sample $\sn=(X_1,...,X_n)$ where $(\stn) \in A$. In
order to bound $\sigma$ we shall estimate the probability that a
coordinate projection has a small diameter in $\ell_2^n$.
\begin{Theorem}\label{corollary:truempballs} 
Let $F$ be a class of functions which map $\Omega$ into $[-1,1]$. For
every $x>0$ and $r$ which satisfies that
  \[
    \E \sup_{f \in F, \ \E_\mu f^2 \leq r} \big|\sum_{i=1}^n \eps_i f(X_i) \big|
   \leq \frac{nr}{20} -  \frac{11x}{20} ,
  \]
then with probability at least $1-2e^{-x}$,
  \[
 \Bigl\{f \in F : \ \E_\mu f^2\le r\Big\} \subset
      \Big\{f\in F : \ \sum_{i=1}^n f^2(X_i)\le 2rn \Big\}.
  \]
\end{Theorem}
\proof
The proof follows directly from the contraction inequality \citep[see, e.g., Theorem
2.8 in][]{BBM2} for $\phi(x) = x^2$ combined with Corollary 2.7 in \citet{BBM2}.
\endproof
By our selection of $t$, it is easy to see that there is an
absolute constant $c$, such that if $x=cnt$, then with probability
larger that $1-2e^{-cnt}$, the radius of the projected set
$\Ft/\sn \subset \ell_2^n$ is smaller than $\sqrt{2nt}$. In
particular, we have
\begin{Corollary}
There are absolute constants $c$ and $c_1$ for which the following
holds. For every $t \geq c_1/n$ such that $\E Z_t \leq nt/16$,
there is a set $A_t'$ of samples $(\stn)$ which has
probability larger than $1-3e^{-cnt}$, on which the set
$V=\bigl\{\big(f(X_1),...,f(X_n)\bigr) : \ f \in \Ft \bigr\}$
is such  that $\E_\eps \sup_{v \in V} |\sum_{i=1}^n \eps_i v_i |
\leq nt/8$ and $\sup_{v \in V} \|v\|_{\ell_2^n} \leq \sqrt{2nt}$.
\end{Corollary}
Combining this corollary with Theorem \ref{thm:conc-rad}, for
every such set $V$,
\begin{equation*}
Pr_\eps \Bigl\{ \sup_{v \in V} \Big| \sum_{i=1}^n \eps_i v_i \Big|
\geq \frac{nt}{4} \Bigr\} \leq Pr_\eps \Bigl\{ \sup_{v \in V}
\Big| \sum_{i=1}^n \eps_i v_i\Big| \geq \E_\eps \sup_{v \in V}
\big| \sum_{i=1}^n \eps_i v_i \big| +\frac{nt}{8} \Bigr\} \leq
4e^{-cnt}
\end{equation*}
for an absolute constant $c$. Hence, there are absolute constants
$c$ and $K$ such that
\begin{equation} \label{eq:div-learning}
Pr_{\X \times \Y}Pr_\eps \Bigl\{\exists f \in \Ft, \
\Bigl|\sum_{i=1}^n \eps_i f(X_i) \Bigr| \geq \frac{nt}{4} \Bigr\}
\leq Ke^{-cnt}.
\end{equation}

\noindent {\bf Proof of Theorem \ref{thm:learning}.} For every
$t>0$ let $\Fn=\Fnsym \ass \Ft$, and thus Assumption \ref{ass} holds
with $\delta=0$. Since for every $f \in \Ft$, $\E_\mu f^2 \leq t$,
then
$$
\bigl(1-\frac{4}{nt^2}\sup_{f \in \Ft} \text{var}(f)\bigr) \geq
\frac{1}{2}
$$
provided that $t \geq 8/n$. Now the assertion follows from \eqref{eq:var}, Theorem
\ref{thm:main}, and \eqref{eq:div-learning}.
\endproof

\subsection{Luckiness} \label{sec:luck}

In the luckiness framework introduced in \citet{luck}, bounds on
the generalization error of functions are formulated {\em a posteriori},
after having seen a sample \sn. The bounds are given in terms of
an upper bound on some empirical, computable quantity dependent on
the sample.

%The main idea driving the luckiness proof is that one wants to exploit
%additional knowledge regarding the actual sample and the function class.
%This knowledge is quantified through a luckiness function. If this luckiness
%function is known and has the property that covering numbers of so called 
%``lucky sets" of functions (dependent on the luckiness on double-samples)
%can be upper bounded with high probability by a function dependent only 

In the following, let $n$ be a fixed sample size, $d$ is a given
fixed integer, and set  $\delta \in (0,1]$.
Three concepts are used in the luckiness framework. The first is
the luckiness function $L: F \times \cup_k \, \Omega^k
\longrightarrow \mathbb{R}$ which is invariant under permutations
of the sample, that is, it depends only on the set
$\{x_1,...,x_k\}$. 

Using the luckiness function one can construct
sample dependent subsets of $F$, called {\it lucky sets} in the
following manner; for every sample $\Zs$ and $f \in F$, the lucky
set consists of all the functions luckier on this sample than the
given function, that is,
 \BE
 \luckyset{f}{\Zs} \ass  \bigl\{g \in F: L(g,\Zs) \geq
 L(f,\Zs)\bigr\}.
\nonumber
 \EE
Observe that the luckiness function  imposes a structure of
increasing subsets of $F$, because $\luckyset{g}{\Zs} \subseteq
\luckyset{f}{\Zs}$ if and only if $L(g,\Zs) \geq L(f,\Zs)$, a fact which
will allow us to define $\Fnsym(\stn)$.

\begin{Lemma}
For every integer $d$ and sample $\Zs$ there is a unique set
$H_d(\Zs)$ with the following properties:

\begin{enumerate}
\item $\packno{\frac{1}{n}}{H_d(\Zs)}{L_1(\mu_{n})} \leq 2^d$,
where $\mu_n$ is the empirical measure supported on $\Zs$.

\item If $f \in F$ satisfies that
$\packno{\frac{1}{n}}{\luckyset{f}{\Zs}}{L_1(\mu_{n})} \leq 2^d$
then $f \in H_d(\Zs)$.
\end{enumerate}
\end{Lemma}

 \proof
Let $A \ass \{f \in F \, : \,
\packno{\frac{1}{n}}{\luckyset{f}{\Zs}}{L_1(\mu_{n})} \leq 2^d \}$
and set $H_d(\Zs) \ass \underset{f \in A}{\bigcup} \luckyset{f}{\Zs}$. To
see that $H_d(\Zs)$ has the required properties, note that if $K
\subset H_d(\Zs)$ is a finite $1/n$-separated set with respect to
$L_1(\mu_n)$, then there is some $f \in A$ such that $K \subset
\luckyset{f}{\Zs}$, implying that $|K| \leq 2^d$. The second
property and the uniqueness are easily verified.
\endproof

For every double-sample $\Zs = (\stn)$ we set
 \BE
 \Fnsym(\stn)  \ass H_d(\stn),
\label{rslFtwoN}
 \EE
and observe that this random class is permutation invariant,
implying that $\Fnsym$ is symmetric.

The second ingredient in the luckiness framework, the 
 $\,\omega$-function, $\omega: \mathbb{R} \times \mathbb{N} \times
(0,1] \rightarrow \mathbb{N}$, is used to define
$\Fn(\sn)$. Given a luckiness function $L$ and an
$\omega$-function, then for a fixed integer $d$ and $\delta \in
(0,1]$, define
 \BE
  \Fn(\sn) \ass \bigl\{ f \in F: \ \omegaf{\sn} \leq 2^d
  \bigr\}.
 \label{rslFN}
 \EE

The third ingredient is the $\omega$-smallness condition, which  is a joint property of
the luckiness and $\omega$ functions. It states that for every $n
\in \mathbb{N}$,
 every $\delta \in (0,1]$ and every probability measure $\mu$
 \BE
 Pr_{\X \times \Y} \Bigl\{\exists f \in F:
 \packno{\frac{1}{n}}{\luckyset{f}{(\stn)}}{L_1(\mu_{2n})} > \omegaf[\delta]{\sn}
 \Bigr\} < \delta.
\label{rslomegasmallns}
 \EE

Examples for luckiness functions are the empirical
VC-dimension of a binary  function class with respect to a sample---in this
case all lucky sets are  equal to the whole set $F$---and the margin of  linear classifiers. Their corresponding 
$\omega$ functions can be found in \citet{luck}.
Although the luckiness framework gives a unified proof for existing 
generalization bounds, finding a pair of luckiness and $\omega$-functions
seems to be difficult,
 because of the quite technical
and counterintuitive $\omega$-smallness condition.


The following result shows that the $\omega$-smallness of $L$  ensures
that Assumption \ref{ass} holds, and that, with high probability,
$\Fnsym(\stn)/\sn$ is sufficiently small. Therefore, it is just a way
of requiring that $\Fnsym(\stn)$ has, with high probability, 
small random coordinate projections.

\begin{Lemma} \label{lemma:luckysymmcond}
For fixed integers $n$ and $d$, and $\delta \in (0,1]$, let $\Fn$
and $\Fnsym$  be defined as in \eqref{rslFN} and \eqref{rslFtwoN}.
If a luckiness function $L$ and an $\omega$-function satisfy the
$\omega$-smallness condition \eqref{rslomegasmallns}, then for
every $t>0$,

\begin{multline}
Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fn(\sn), \
\absdiffmean{f}{X}{Y} \geq t \Bigr\} \\
\leq Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fnsym(\stn), \
\absdiffmean{f}{X}{Y} \geq t \Bigr\} +  \delta. \nonumber
\end{multline}
\end{Lemma}

\proof For a fixed double sample $\Zs =(\stn)$  let
$\mu_{2n}$ be the empirical measure supported on $\Zs$. Put
$$A_{\Zs} \ass
\Bigl\{ f \in F \ : \,
\packno{\frac{1}{2n}}{\luckyset{f}{(\stn)}}{L_1(\mu_{2n})}
\leq \omegaf{\sn} \Bigr\}$$ and
$$B_{\Zs} \ass \Bigl\{ f \in F : \,
\packno{\frac{1}{2n}}{\luckyset{f}{(\stn)}}{L_1(\mu_{2n})}
\leq 2^d \Bigr\}.$$ Note that $\Fn(\sn) \cap A_{\Zs} \subseteq B_{\Zs}
\subseteq \Fnsym(\stn)$. By the $\omega$-smallness
condition,
$$
Pr_{\X \times \Y} \{\exists f \in (A_{\Zs})^c \} \leq \delta,
$$
and by
the union bound for disjoint sets,
\begin{multline}
Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fn(\sn), \
\absdiffmean{f}{X}{Y} \geq t \Bigr\}  \\
= Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fn(\sn) \cap A_{\Zs}, \ \absdiffmean{f}{X}{Y} \geq t \Bigr\} \\
+ Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fn(\sn) \cap (A_{\Zs})^c, \
\absdiffmean{f}{X}{Y} \geq t \Bigr\},
\end{multline}
and our claim follows.
\endproof
%\end{itemize}

Now, we are ready to formulate the generalization bound for the
luckiness framework.
\begin{Theorem}\label{theorem:luckiness}
Let L and $\omega$ be functions satisfying the $\omega$-smallness
condition \eqref{rslomegasmallns}. Then, for every probability
measure $\mu$, every $d \in \mathbb{N}$ and every $\delta \in
(0,1]$, there is a set of probability larger than $1-12\delta$
such that if $\omegaf{\sn} \leq 2^d$, then
$$
\Big|\E_\mu f -\frac{1}{n}\sum_{i=1}^n f(X_i) \Big| \leq C
\sqrt{\frac{d}{n}\log \frac{1}{\delta}},
$$
where $C$ is an absolute constant.
\end{Theorem}


\proof Let $\Fn$ and $\Fnsym$  be defined as above, and observe
that
\BE
\packno{\frac{1}{n}}{\Fnsym(\stn)}{L_1(\mu_{2n})}
\leq 2^d 
\label{obspacksm}
\EE
for every $(\stn)$. By Corollary \ref{cor:main} we
have to estimate
$$
Pr_{\X \times \Y} \Bigl\{\E_\eps \sup_{f \in  \Fnsym(\stn)}
\Bigl|\sum_{i=1}^n \eps_i f(X_i) \Big| > \frac{nt}{8} \Bigr\},
$$
where $\sn=(X_1,...,X_n)$ and  $\tn=(Y_1,...,Y_n)$. Let
$$
V \ass \Big\{ \big(f(X_1),...,f(X_n)\bigr): f \in \Fnsym(\stn)
\Bigr\} \subset \ell_2^n,
$$
put $\mu_{2n}$ to be the empirical measure supported on
$\Zs=(\stn)$ and set $\nu_n$ to be the empirical measure
supported on $\sn$. Note that for every $f,g$, $\E_{\mu_{2n}}
|f-g| \geq \E_{\nu_n} |f-g|/2$. Thus, every $1/n$-cover of
$\Fnsym(\stn)$ in $L_1(\mu_{2n})$ is a $2/n$-cover of the
same set in $L_1(\nu_n)$. In particular, if $A$ is a maximal
$1/n$-packing of $\Fnsym(\stn)$ in $L_1(\mu_{2n})$, it is a
$2/n$ cover of that set in $L_1(\nu_n)$. It is easy to verify that
$B\bigl(L_1(\nu_n)\bigr)=nB_1^n$, and in particular, $V \subset
A+\frac{2}{n} \cdot nB_1^n =A+2B_1^n$, where $A+B=\{a+b \ : a \in
A, \ b \in B\}$. By the triangle inequality,

\begin{align*}
\E_\eps \sup_{f \in \Fnsym(\stn)} \Big|\sum_{i=1}^n \eps_i
f(x_i) \Big| 
&= 
\E_\eps \sup_{v \in V} \Big|\sum_{i=1}^n \eps_i v_i \Big| 
=\E_\eps \sup_{a \in A, \, b \in B_1^n}
\Big|\sum_{i=1}^n \eps_i (a_i + 2b_i) \Big| \\
&\leq \E_\eps \sup_{a \in A} \Big|\sum_{i=1}^n \eps_i a_i \Big| +
2\E_\eps \sup_{b \in B_1^n} \Big|\sum_{i=1}^n \eps_i  b_i \Big|. 
\end{align*}

The first term can be bounded by a corollary of Slepian's
inequality \citep{Pis89}, which states that there is an absolute
constant $C$ such that for every $A \subset \ell_2^n$,

\BE \E_g \sup_{a \in A} \Big|\sum_{i=1}^n g_i a_i \Big| \leq C
\sqrt{\log |A|} \sup_{u,v \in A} \| u-v \|_2, \nonumber \EE where
$(g_i)_{i=1}^n$ are independent standard gaussian random
variables.

Since our class consists of functions bounded by $1$, then $V
\subset B_\infty^n \subset \sqrt{n}B_2^n$ and since the Rademacher
averages are upper bounded (up to an absolute constant) by the
gaussian ones \citep{MilSche01},
 then
 \BE \E_\eps \sup_{a \in A}
\Big|\sum_{i=1}^n \eps_i a_i \Big| \leq C \E_g \sup_{a \in A}
\Big|\sum_{i=1}^n g_i a_i \Big| \leq C \sqrt{\log |A|} \sqrt{n}
\leq C \sqrt{nd}, \nonumber \EE where the final inequality holds
because $|A| \leq 2^d$ by \eqref{obspacksm}.


In order to estimate the second term, one can apply the triangle inequality to
show that 
\BE \E_\eps \sup_{b \in B_1^n} \Big| \sum_{i=1}^n \eps_i  b_i
\Big| \leq 1. \nonumber \EE

In conclusion \BE \E_\eps \sup_{f \in \Fnsym(\stn)}
\Big|\sum_{i=1}^n \eps_i f(x_i) \Big| \leq C \sqrt{nd}. \nonumber
\EE

To complete the proof, apply Corollary \ref{cor:main} for
$t=C\sqrt{\frac{d}{n}\log(1/\delta)}$.
\endproof




\subsection{Algorithmic Luckiness} \label{sec:algoluck}


In the algorithmic luckiness framework \citep{algoluck}, the generalization error
bound is also formulated {\em a posteriori}, after having seen a sample.
It differs from  the luckiness framework because it gives bounds
on the generalization error of the  function  learned by the
learning algorithm from the sample at hand. Again, the bound is
given in terms of  a computable quantity dependent on the sample
and on the algorithm.

In a similar fashion to the luckiness framework, an algorithmic
luckiness function and an $\omega$-function are introduced in
order to define the functions  $\Fn$ and $\Fnsym$. The functions $L$ and
$\omega$ satisfy a joint smallness condition which ensures that
Assumption \ref{ass} holds, and that the size of the projection
$\Fnsym(\stn)/\sn$ is sufficiently small.

As we did before, fix  a sample size $n$, an integer $d$ and some
$\delta \in (0,1]$. Denote by ${\cal A}$ a fixed learning
algorithm, by ${\cal A}(\Zs)$ the loss function associated with the hypothesis produced by the algorithm
from the sample $\Zs$, and set ${\cal A}(F)=\{f={\cal A}(\Zs): \ \Zs \in
\Omega^n\}$.

The algorithmic luckiness function is a function $L: {\cal A}(F)
\longrightarrow \mathbb{R}$. For a sample $\Zs$ of size $2n$, the
{\it lucky set} $\aluckyset{\Zs}$ is defined as the subset  of losses of 
functions learned by the algorithm on the first half of the
sample, when permuting the whole sample, as long as the function
the algorithm produced on the first half of the permuted sample is
``luckier" than on the original one. Formally, let $S_{2n}$ be the
set of permutations on $\{1,...,2n\}$, and for every
$\Zs=(\Zs_1,...,\Zs_{2n})$, set $\Zs|_{i=1}^n=(\Zs_1,...,\Zs_n)$. Define the
lucky set as 
\BE \aluckyset{\Zs} \ass \Bigl\{{\cal
A}\bigl(\pi(\Zs)|_{i=1}^n\bigr): \ L\bigl({\cal
A}(\pi(\Zs)|_{i=1}^n)\bigr) \geq L\bigl({\cal A}( \Zs|_{i=1}^n
)\bigr), \  \pi \in S_{2n} \Bigr\}. \nonumber \EE

If $G_{\cal A}(\Zs)$ is the subset of losses corresponding to functions  learned by
${\cal A}$ on the first half of all the permutations of the
double-sample $\Zs$, then $G(\Zs) \subset G_{\cal A}(\Zs)$, and clearly,
$|G_{\cal A}(\Zs)| \leq (2n)!<\infty$. Therefore, we can order the
functions in decreasing order according to their luckiness. Define the
ordered set

\BE G_{\cal A}(\Zs) \ass \Bigl[
\underset{\aluckyset{\Zs}}{\underbrace{f_1 , f_2, f_3, \dots,
f_{{k-1}}, f_{k}}}, f_{{k+1}},\dots, f_m \Bigr], \nonumber \EE
and for the sake of simplicity,  assume that for every $i<j$,
$L(f_i)>L(f_j)$. Only a small modification is required in the general
case, where some functions might have the same luckiness.

Set $f_{k}={\cal A}(\Zs|_{i=1}^n)$ and let
$\afirstset[\ell]{\Zs}$ be the subset consisting of the first $\ell$
functions in $G_{\cal A}(\Zs)$, that is, $\afirstset[\ell]{\Zs} = \{
f_{1} , f_{2}, f_{3}, \dots, f_{\ell} \}$.
 %%%%

For the given integer $d$ and the  double-sample $(\stn)$ put
$k^*$ to be the largest integer such that \BE
\packno{\frac{1}{n}}{\afirstset[k^*]{(\stn)}}{L_1(\mu_{2n})} \leq 2^d \text{ and }
\packno{\frac{1}{n}}{\afirstset[k^*+1]{(\stn)}}{L_1(\mu_{2n})} >
2^d. \nonumber \EE 
Then, by setting \BE
\label{rsalFtwoN} \Fnsym(\stn)  \ass
\afirstset[k^*]{(\stn)} \EE 
it follows that \Fnsym is
symmetric, since the learning algorithm is permutation invariant.

The $\omega$-function, $\omega: \mathbb{R} \times \mathbb{N}
\times (0,1] \longrightarrow \mathbb{N}$ is used to define
$\Fn(\sn)$. Indeed, define 
\BE \label{rsalFN} \Fn(\sn) \ass
\begin{cases}
\{{\cal A}(\sn)\} & \text{if} \  \omegafa{\sn} \leq 2^d \\
\emptyset & \text{otherwise},
\end{cases}
\EE and note that $|\Fn(\sn)| \leq 1$.

Finally, the $\omega$-smallness condition states that for every
integer $n$, every $\delta \in (0,1]$, and every probability
measure $\mu$, \BE \label{rsalomegasmallns} P_{\X \times \Y} \Bigl\{
\packno{\frac{1}{n}}{\aluckyset{(\stn)}}{L_1(\mu_{2n})} \geq
\omegafa{\sn} \Bigr\} < \delta, \EE and as we show, it assures
that  Assumption \ref{ass} holds.

\begin{Lemma}
\label{lemma:algoluckysymmcond}
Let ${\cal A}$ be a learning algorithm,  fix an integer $d$ and some  $\delta
\in (0,1]$, and let $\Fn$ and $\Fnsym$
be  as in \eqref{rsalFN} and \eqref{rsalFtwoN}. If a  luckiness function and $\omega$-function
satisfy the $\omega$-smallness condition \eqref{rsalomegasmallns}, then for
every  $t>0$
\begin{multline}
Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fn(\sn):
\absdiffmean{f}{X}{Y} \geq t \Bigr\} \\
\leq Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fnsym(\stn):
\absdiffmean{f}{X}{Y} \geq t \Bigr\} + \delta. \nonumber
\end{multline}

\end{Lemma}
\proof For every double sample $\Zs=(\stn)$, let $\mu_{2n}$ be the empirical
measure supported on $(\stn)$ and define two random
sets in the following manner. Let $A_{\Zs} \ass \{{\cal A}(\sn)\}$ if
$\packno{\frac{1}{n}}{\aluckyset{{(\stn)}}}{L_1(\mu_{2n})} <
\omegafa{\sn}$ and the empty set otherwise, and put $B_{\Zs} \ass \{
{\cal A}(\sn)\}$ if
$\packno{\frac{1}{n}}{\aluckyset{{(\stn)}}}{L_1(\mu_{2n})}
\leq 2^d$ and the empty set otherwise. Note that for every $\Zs$,
$\Fn(\sn) \cap A_{\Zs} \subset B_{\Zs} \subset \Fnsym(\stn)$.
Moreover, if $\Fn(\sn) \cap (A_{\Zs})^c \not = \emptyset$, then
$\Fn(\sn)=\{{\cal A}(\sn)\}$ and $A_{\Zs} =\emptyset$. Thus, by the
$\omega$-smallness condition,
\begin{equation*}
Pr_{\X \times \Y} \Bigl\{\Fn(\sn) \cap (A_{\Zs})^c \not = \emptyset
\Bigr\} \leq Pr_{X \times Y} \Bigl\{A_{\Zs} =\emptyset \Bigr\} <
\delta.
\end{equation*}
Finally, for every $t>0$,
\begin{align*}
P_{\X \times \Y} \Bigl\{ \exists f &\in \Fn(\sn), \
\Big|\diffmean{f}{X}{Y}\Big| \geq t \Bigr\}  \\
&=
Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fn(\sn) \cap A_{\Zs}, \ \absdiffmean{f}{X}{Y} \geq t \Bigr\} \\
&+ Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fn(\sn) \cap
\bigl(A_{\Zs}\bigr)^c, \ \absdiffmean{f}{X}{Y} \geq t \Bigr\}
\\
&\leq Pr_{\X \times \Y} \Bigl\{ \exists f \in \Fnsym(\stn), \
\absdiffmean{f}{X}{Y} \geq t \Bigr\} + \delta, 
\end{align*}
as claimed.
\endproof

The definition of $\Fnsym(\stn)$ assures that the covering
numbers of $\Fnsym(\stn)$ are small, and by Corollary
\ref{cor:main} we obtain a result analogous to Theorem
\ref{theorem:luckiness}, which recovers the main result of
\citet{algoluck}.

\begin{Theorem}\label{theorem:algoluckiness}
Let ${\cal A}$ be a learning algorithm which takes values in
$\bi$, and let $L$ and $\omega$ be functions satisfying the
$\omega$-smallness condition \eqref{rsalomegasmallns}. Then, for
every probability measure $\mu$, every $d \in \mathbb{N}$ and
every $\delta \in (0,1]$, there is a set of probability at least
$1-12\delta$ such that if $\omegafa{\sn} \leq 2^d$, then
$$
\Bigl|\E_\mu \bigl({\cal A}(\sn)\bigr)-\E_{\mu_n} \bigl({\cal
A}(\sn)\bigr)\Bigr| \leq C\sqrt{\frac{d}{n}\log \frac{1}{\delta}},
$$
where $C$ is an absolute constant.
\end{Theorem}

\section*{Acknowledgements} We would like to thank Ran Bachrach, Olivier Bousquet,
Gideon Schechtman, and Bob Williamson for their valuable suggestions and comments.


\thebibliography{}

\bibitem[Alon et al.(1997)]{ABCH} N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler.
Scale-sensitive dimensions, uniform convergence, and learnability.
{\it Journal of the ACM}, vol. 44(4), 615-631, 1997.

\bibitem[Bartlett, Bousquet, and Mendelson(2004)]{BBM2} P. L. Bartlett, O. Bousquet,
  and S. Mendelson. 
Local Rademacher complexities. {\it The Annals of Statistics},  2004, to appear.

\bibitem[Bartlett,  Jordan, and McAuliffe(2003)]{BJA} P. L. Bartlett,
 M. I. Jordan, and J. D. McAuliffe.
 Convexity, classification, and risk bounds. Technical Report 638, 
Department of Statistics, UC Berkeley, 2003.

\bibitem[Boucheron,  Lugosi, and Massart(2003)]{BLM2} S. Boucheron, G. Lugosi,
  and P. Massart. 
Concentration inequalities using the entropy method. {\it The Annals of Probability}, 
vol 31(3), 1583--1614, 2003. 

\bibitem[Bousquet(2002)]{Bou02} O. Bousquet. A Bennett concentration inequality
and its application to suprema of empirical processes. {\it Comptes-Rendus de l'Acad\'emie Scientifique de Paris}, Ser. I, 334, 495--500, 2002.

\bibitem[Cannon et al.(2002)]{CanEtt02} A. H. Cannon, J. M. Ettinger,
  D. R. Hush,
  and J. C. Scovel. 
Machine learning with data dependent hypothesis classes. {\it Journal of Machine
Learning Research}, 2, 335--358, 2002.

\bibitem[Gat(1999)]{Gat99} Y. Gat. A bound concerning the generalization ability of a
  certain class of learning algorithms. Technical Report 548, UC Berkeley, March 1999.

\bibitem[Herbrich and Williamson(2002)]{algoluck} R. Herbrich and R. C. Williamson. Algorithmic
luckiness. {\it Journal of Machine Learning Research}, 3, 175--212, 2002.

\bibitem[Johnson and Schechtman(1991)]{John-Sch} W. B. Johnson and G. Schechtman. A remark on
Talagrand's deviation inequality for Rademacher functions. In {\it  Functional
  Analysis (Austin, TX, 1987/1989)}, 
Lecture Notes in Mathematics 1470, 72--77, Springer, 1991.

\bibitem[Ledoux(2001)]{Ledoux} M. Ledoux. {\it The concentration of measure
phenomenon}. Mathematical Surveys and Monographs, Vol 89, AMS,
2001.

%\bibitem[Lee, Bartlett, and Williamson(1996)]{LBW} W.S. Lee, P.L. Bartlett, R. C. Williamson. 
%Efficient Agnostic Learning of Neural Networks with Bounded Fan-in, 
%IEEE Transactions on Information Theory, 42(6), 2118-2132, 1996. 

\bibitem[Lee, Bartlett, and Williamson(1998)]{LBW} W. S. Lee, P. L. Bartlett,
  and R. C. Williamson.
The importance of convexity in learning with squared loss. {\it IEEE Transactions
  on Information Theory}, 44(5), 1974--1980, 1998.

\bibitem[McDiarmid(1989)]{McDia89}
C. McDiarmid. On the method of bounded differences. In {\it Surveys
in Combinatorics}, London Mathematical Society
Lecture Note Series 141,
148--188, Cambridge University Press, 1989.

\bibitem[Mendelson(2002a)]{Men:GC} S. Mendelson. Rademacher averages and phase
transitions in Glivenko-Cantelli classes. {\it IEEE Transactions on
Information Theory}, 48(1), 251--263, 2002a.

\bibitem[Mendelson(2002b)]{Men:smallsets} S. Mendelson. Improving the sample
  complexity using global data. {\it IEEE Transactions on Information Theory}, 
48(7), 1977--1991, 2002b.

\bibitem[Mendelson(2003)]{Men:summer} S. Mendelson. A few notes on Statistical Learning
Theory. In {\it Proceedings of the Machine Learning Summer School,
Canberra 2002, S. Mendelson and A. J. Smola (Eds.)}, 
Lecture Notes in Computer Sciences LNCS 2600, 1--40, Springer, 2003.

\bibitem[Mendelson and Philips(2003)]{MenPhi03} S. Mendelson and P. Philips.
    Random subclass bounds. In 
    {\it Proceedings of the 16th Annual Conference on Computational Learning
    Theory}, 329--343, Springer, 2003.

\bibitem[Mendelson and Vershynin(2003)]{MenVer} S. Mendelson and R. Vershynin. Entropy and the combinatorial
dimension. {\it Inventiones Mathematicae}, 152, 37--55, 2003.

\bibitem[Milman and Schechtman(2001)]{MilSche01}
V. D. Milman and G. Schechtman. {\it Asymptotic Theory of Finite Dimensional
Normed Spaces}. Lecture Notes in Mathematics 1200, Springer, 2001.

\bibitem[Pisier(1989)]{Pis89} G. Pisier.
{\it The Volume of Convex Bodies and Banach Space Geometry}.
Cambridge University Press, 1989.

\bibitem[Shawe-Taylor et al.(1998)]{luck} J. Shawe-Taylor, P. L. Bartlett,
  R. C. Williamson, and M. Anthony. Structural risk minimization over data-dependent
hierarchies. {\it IEEE Transactions on Information Theory}, 44(5),
1926--1940, 1998.

\bibitem[Talagrand(1996)]{Tal-GenCh96} M. Talagrand. Majorizing measures: The generic chaining.
  {\it The Annals of Probability}, 24, 1049--1103, 1996.

\bibitem[Talagrand(1995)]{Tal-conv} M. Talagrand. Concentration of measure and
isoperimetric inequalities in product spaces. {\it Publications
Math\'{e}matiques de l'I.H.E.S.} 81, 73--205, 1995.

%\bibitem{Vap98} V. Vapnik: The Nature of Statistical Learning Theory,
%  Springer, 2000.

\bibitem[Vapnik and Chervonenkis(1971)]{VC} V. Vapnik and A. Chervonenkis. On the uniform
  convergence of relative frequencies of events to their probabilities. 
  {\it Theory of Probability and its Applications},
  16(2), 264--280, 1971.
\end{document}
























