Empirical risk minimization for heavy-tailed losses
\fnms{Christian
\fnms{Emilien
\fnms{G\'abor
Christian Brownlees\ead[label=e1]{christian.brownlees@upf.edu
Emilien Joly\ead[label=e2]{emilien.joly@ens.fr
G\'abor Lugosi\thanksref{t3
The purpose of this paper is to discuss empirical risk minimization when the losses are not necessarily bounded and may have a distribution with heavy tails. In such situations usual empirical averages may fail to provide reliable estimates and empirical risk minimization may provide large excess risk. However, some robust mean estimators proposed in the literature may be used to replace empirical means. In this paper we investigate empirical risk minimization based on a robust estimate proposed by Catoni. We develop performance bounds based on chaining arguments tailored to Catoni's mean estimator.
erm.tex
\documentclass[aos]{imsart}

%\documentclass[11pt]{article}

\usepackage{geometry}
%%\usepackage[tbtags]{amsmath}
\usepackage{amsthm}
%\usepackage{graphicx}
\usepackage{amssymb}
%\usepackage{epstopdf}
\usepackage{dsfont}

%\usepackage{fullpage}
%\usepackage[T1]{fontenc}
%\usepackage{euler}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{bbm}      
\usepackage[numbers,sort&compress]{natbib}

\usepackage{graphicx} % to include and manipulate graphics
\usepackage[all]{xy} % to draw diagrams
%\usepackage{psfrag} % to addlatex into eps files
%\usepackage{pstricks,pst-node}
%\usepackage{pstricks-add}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{defi}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conj}[theorem]{Conjecture}
%\newtheorem{example}[theorem]{Example}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}

\newenvironment{proofof}[1]{\par\noindent{\bf Proof of #1:}}{\qed \par\medskip\noindent}
\newenvironment{defproof}[1]{\par\noindent{\bf Proof~#1:}}{\qed \par\medskip\noindent}

\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\R}{\field{R}}
\newcommand{\E}{\field{E}}
\newcommand{\EXP}{\E}
\newcommand{\PROB}{\field{P}}
\renewcommand{\Pr}{\PROB}
\newcommand{\IND}[1]{\mathbbm{1}_{\{ #1 \}}}
%\newcommand{\IND}[1]{\field{I}_{\{#1\}}}
\newcommand{\Var}{\mbox{Var}}
\newcommand{\dt}{\displaystyle}
\renewcommand{\ss}{\subseteq}
\newcommand\theset[2]{ \left\{ {#1} \,:\, {#2} \right\} }
\newcommand{\norm}[1]{\left\|{#1}\right\|}
\newcommand{\argmin}{\mathop{\rm argmin}}
\newcommand{\argmax}{\mathop{\rm argmax}}
\newcommand{\esssup}{\mathop{\rm ess sup}}
\newcommand{\defeq}{\stackrel{\rm def}{=}}
\newcommand{\sgn}{\mbox{\sc sgn}}
\newcommand{\trace}{\mathrm{Tr}}
\newcommand{\diag}{\mathrm{Diag}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\Y}{\mathcal{Y}}
\newcommand{\Z}{\mathcal{Z}}
\newcommand{\scF}{\mathcal{F}}
\newcommand{\scN}{\mathcal{N}}
\newcommand{\scS}{\mathcal{S}}
\newcommand{\scT}{\mathcal{T}}
\newcommand{\ba}{\boldsymbol{a}}
\newcommand{\be}{\boldsymbol{e}}
\newcommand{\bx}{\boldsymbol{x}}
\newcommand{\bX}{\boldsymbol{X}}
\newcommand{\bY}{\boldsymbol{Y}}
\newcommand{\bxi}{\boldsymbol{\xi}}
\newcommand{\bzeta}{\boldsymbol{\zeta}}
\newcommand{\bq}{\boldsymbol{q}}
\newcommand{\bu}{\boldsymbol{u}}
\newcommand{\bv}{\boldsymbol{v}}
\newcommand{\bw}{\boldsymbol{w}}
\newcommand{\bV}{\boldsymbol{V}}
\newcommand{\lambdamin}{\lambda_{\mathrm{min}}}
\newcommand{\btheta}{\boldsymbol{\theta}}
\newcommand{\bzero}{\boldsymbol{0}}
\newcommand{\loss}{\ell}
\newcommand{\hloss}{\widehat{\ell}}
\newcommand{\bloss}{\boldsymbol{\ell}}
\newcommand{\tloss}{\widetilde{\ell}}
\newcommand{\btloss}{\widetilde{\boldsymbol{\ell}}}
\newcommand{\tL}{\widetilde{L}}
\newcommand{\Lhat}{\widehat{L}}
\newcommand{\Pot}{\Phi}
\newcommand{\bool}{\{0,1\}}
\newcommand{\bvbar}{\overline{\bv}}
\newcommand{\bwbar}{\overline{\bw}}
\newcommand{\Mbar}{\overline{M}}
\newcommand{\wbar}{\overline{w}}
\newcommand{\Wbar}{\overline{W}}
\newcommand{\tB}{\widetilde{B}}



%List of Todo's
\usepackage{tikz}

% Command for inserting a todo item
\newcommand{\todo}[1]{%
% Add to todo list
\addcontentsline{tdo}{todo}{\protect{#1}}%
%
\begin{tikzpicture}[remember picture, baseline=-0.75ex]%
\node [coordinate] (inText) {};
\end{tikzpicture}%
%
% Make the margin par
\marginpar{%
\begin{tikzpicture}[remember picture]%
\definecolor{orange}{rgb}{1,0.5,0}
\draw node[draw=black, fill=orange, text width = 3cm] (inNote)
{#1};%
\end{tikzpicture}%
}%
%
\begin{tikzpicture}[remember picture, overlay]%
\draw[draw = orange, thick]
([yshift=-0.2cm] inText)
-| ([xshift=-0.2cm] inNote.west)
-| (inNote.west);
\end{tikzpicture}%
%
}% 

\makeatletter \newcommand \listoftodos{\section*{Todo list} \@starttoc{tdo}}
\newcommand\l@todo[2]
{\par\noindent \textit{#2}, \parbox{10cm}{#1}\par} \makeatother

\newcommand{\ol}{\overline}
\newcommand{\wh}{\widehat}
\newcommand{\wt}{\widetilde}
\newcommand{\wb}{\overline}
\newcommand{\diam}{\mathop{diam}}
\newcommand{\hf}{\wh{f}}
\newcommand{\hr}{\wh{r}}
\newcommand{\br}{\wb{r}}
\newcommand{\BF}{B_{\F}(\delta)}
\newcommand{\AF}{A_{\F}(\delta)}
\newcommand{\ep}{\varepsilon}


\newcommand{\stochge}{\stackrel{\rm st.}{\ge}}

\newcommand{\example}{\medskip\noindent{\bf Example.} \ }
\newcommand{\remark}{\medskip\noindent{\bf Remark.} \ }



\newtheorem{de}{Definition}
\newtheorem{rem}{Remark}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{thm}[theorem]{Theorem}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{lem}[theorem]{Lemma}

%Commands specific to the paper
\newcommand{\F}{\mathcal{F}} %The class F
\newcommand{\G}{\mathcal{G}} %The class G
\newcommand{\prob}[1]{\mathbb{P}\left\{#1\right\}} % The probability
\newcommand{\probi}[2]{\mathbb{P}_{#1}\left\{#2\right\}} % The probability with ind
\newcommand{\esp}[1]{\mathbb{E}\left[#1\right]} % The expected value
\newcommand{\espi}[2]{\mathbb{E}_{#1}\left[#2\right]} % The expected value with ind
\newcommand{\var}[1]{\text{Var}\left(#1\right)} % The variance
\newcommand{\vari}[2]{\text{Var}_{#1}\left(#2\right)} % The variance with ind
%\newcommand{\1}[1]{\mathds{1}_{#1}}
\newcommand{\N}{\mathbb{N}} %The integers
\newcommand{\orlic}[2]{\left\|#1\right\|_{\psi_{#2}}} %Orlicz norms
\newcommand{\hyp}[2] {\fbox{\textbf{Hypothesis #1} : #2}\\} %The hypothesis of the paper

\newcommand{\cat}[1]{\hat{\mu}(#1)}

\numberwithin{figure}{section}

\begin{document}
\begin{frontmatter}


\title{Empirical risk minimization for heavy-tailed losses}
\runtitle{Risk minimization for heavy tails}


% \author{\fnms{Christian} \snm{Brownlees}\ead[label=e1]{christian.brownlees@upf.edu}}
% \address{printead{e1}}
% \affiliation{Department of Economics and Business, Pompeu Fabra University}
% \and
% \author{\fnms{Emilien} \snm{Joly}\ead[label=e2]{emilien.joly@ens.fr}}
% \address{\printead{e2}}
% \affiliation{\'Ecole Normale Sup\'erieure, Paris} 
% \and
% \author{\fnms{G\'abor} \snm{Lugosi}\corref{}\ead[label=e3]{gabor.lugosi@upf.edu}\thanksref{t1}}
% \thankstext{t1}{The first and third authors were supported by
% the Spanish Ministry of Science and Technology grant MTM2012-37195.} 
% \address{printead{e3}}
% \affiliation{ICREA and Department of Economics and Business, Pompeu Fabra University}

% \runauthor{Brownlees, Joly, and Lugosi}


\begin{aug}
  \author{Christian Brownlees\ead[label=e1]{christian.brownlees@upf.edu}}
  \and
  \author{Emilien Joly\ead[label=e2]{emilien.joly@ens.fr}}
  \and
\author{G\'abor Lugosi\thanksref{t3}\ead[label=e3]{gabor.lugosi@upf.edu}},
  \address{Department of Economics and Business \\ Pompeu Fabra University\\
          \printead{e1}}

  \address{\'Ecole Normale Sup\'erieure, Paris \\
          \printead{e2}}

  \address{ICREA and Department of Economics and Business \\ Pompeu Fabra University\\
          \printead{e3}}

 \thankstext{t3}{The first and third authors were supported by the Spanish Ministry of Science and Technology grant MTM2012-37195.}

\runauthor{Brownlees, Joly, and Lugosi}

\end{aug}



\begin{abstract}
The purpose of this paper is to discuss empirical risk 
minimization when the losses are not necessarily bounded
and may have a distribution with heavy tails. In such
situations usual empirical averages may fail to provide reliable
estimates and empirical risk minimization may provide large excess risk.
However, some robust mean estimators proposed in the literature
may be used to replace empirical means.
In this paper we investigate empirical risk minimization 
based on a robust estimate proposed by Catoni. 
We develop performance bounds based on chaining arguments
tailored to Catoni's mean estimator. 
\end{abstract}


\end{frontmatter}

\section{Introduction}

Heavy tailed data are commonly encountered in many fields of research (see, e.g., Embrechts, Kl\"uppelberg and Mikosch \cite{Emb97} and Finkenstadt and Rootz\'en \cite{Fin03}).
For instance, in finance, the influential work of Mandelbrot \cite{Man63} and Fama \cite{Fam63} documented evidence of power-law behavior in asset prices in the early 1960's.
When the data have heavy tails, standard statistical procedures typically perform poorly and 
appropriate robust alternatives are needed to carry out inference effectively.
In this paper we propose a class of robust empirical risk minimization
procedures for such data that are based on a robust estimator
introduced by Catoni \cite{Cat10}.

Empirical risk minimization is one of the basic principles of statistical learning that is 
routinely applied in a great variety of problems such as regression function estimation, classification, and clustering. 
The general model may be described as follows. 
Let $X$ be a random variable taking values in some measurable space
$\mathcal{X}$ and let $\F$ be a set of non-negative functions 
defined on $\X$.
For each $f \in \F$, define the {\sl risk} $m_f=\EXP f(X)$ and let 
$m^*=\inf_{f\in \F} m_f$ denote the optimal risk.
In statistical learning $n$ independent random variables
$X_1,\ldots,X_n$ are available, all distributed as $X$, and 
one aims at finding a function with small risk. To this end,
one may define the {\sl empirical risk minimizer} 
\[
  f_{\text{ERM}}= \argmin_{f\in \F} \frac{1}{n} \sum_{i=1}^n f(X_i) \,,
\]
where, for the simplicity of the discussion and essentially
without loss of generality,
we implicitly assume that the minimizer exists.
If the minimum is achieved by more than one function, one may
pick one of them arbitrarily.
 
\remark {\sc (loss functions and risks.)} 
The main motivation and terminology may be explained by
the following general prediction problem in statistical learning. 
Let the ``training data'' $(Z_1,Y_1),\ldots,(Z_n,Y_n)$ be independent identically
distributed pairs of random variables 
where the $Z_i$ take their
values in, say, $\R^m$ and the $Y_i$ are real-valued.
In classification problems the $Y_i$ take discrete values. 
Given a new observation $Z$, one is interested in predicting the
value of the corresponding response variable $Y$ where the pair
$(Z,Y)$ has the same distribution as that of the $(Z_i,Y_i)$.
A predictor is a function $g:\R^m \to \R$ whose quality is measured
with the help of a {\sl loss function} $\ell: \R\times\R \to \R_+$.
The {\sl risk} of $g$ is then $\EXP \ell(g(Z),Y)$.
Given a class $\G$ of functions $g:\R^m \to \R$, empirical risk
minimization chooses one that minimizes the {\sl empirical risk}
$(1/n) \sum_{i=1}^n \ell(g(Z_i),Y_i)$ over all $g\in \G$.
In the simplified notation followed in this paper, $X_i$ corresponds to 
the pair $(Z_i,Y_i)$, the function $f$ represents $\ell(g(\cdot),\cdot)$,
and $m_f$ substitutes $\EXP \ell(g(Z),Y)$.

\medskip

The performance of empirical risk minimization is measured by the
{\sl risk} of the selected function,
\[
   m_{\text{ERM}}= \EXP \left[ f_{\text{ERM}}(X) |X_1,\ldots,X_n \right]~.
\]
In particular, the main object of interest for this paper is
the {\sl excess risk} $m_{\text{ERM}}-m^*$.
The performance of empirical risk minimization has been 
thoroughly studied and well understood using tools of empirical process
theory. In particular, the simple observation that
\[
  m_{\text{ERM}}-m^* 
  \le 2\sup_{f\in \F} \left|\frac{1}{n}\sum_{i=1}^n f(X_i)-m_f\right|\,,
\]
allows one to apply the rich theory on the suprema of empirical
processes to obtain upper performance bounds.
The interested reader is referred to 
Bartlett and Mendelson \cite{BaMe06}, 
Boucheron, Bousquet, and Lugosi \cite{BoBoLu05},
Koltchinskii \cite{Kol06}, 
Massart \cite{Mas06}, 
Mendelson \cite{Men14},
van de Geer \cite{Geer00}
for references and recent results in this area.
Essentially all of the theory of empirical minimization
assumes either that the functions $f$ are uniformly bounded 
or that the random variables $f(X)$ have sub-Gaussian tails for
all $f\in \F$. For example, when all $f\in \F$ take their values
in the interval $[0,1]$, Dudley's \cite{Dud78} 
classical metric-entropy bound, together with standard symmetrization
arguments, imply that there exists a 
universal constant $c$ such that
\begin{equation}
\label{eq:dudley1}
  \EXP m_{\text{ERM}}-m^* 
\le \frac{c}{\sqrt{n}} \EXP \int_0^1 \sqrt{\log N_{\mathbb{X}}(\F,\epsilon)}d\epsilon~,
\end{equation}
where for any $\epsilon>0$,
$N_{\mathbb{X}}(\F,\epsilon)$ is the {\sl $\epsilon$-covering number}
of the class $\F$ under the empirical quadratic distance
$d_{\mathbb{X}}(f,g)= \left(\frac{1}{n}\sum_{i=1}^n (f(X_i)-g(X_i))^2\right)^{1/2}$,
defined as the minimal cardinality
$N$ of any set $\{f_1,\ldots,f_N\}\subset \F$ such that for all
$f\in \F$ there exists an $f_j\in \{f_1,\ldots,f_N\}$ with
$d_{\mathbb{X}}(f,f_j)\le \epsilon$. 
Of course, this is one of the most basic bounds and many important 
refinements have been established. 

A tighter bound may be established by the so-called {\sl generic chaining}
method, see Talagrand \cite{talagrand}. 
Recall the following definition (see, e.g., \cite[Definition 1.2.3]{talagrand}).
Let $T$ be a (pseudo) metric space. An increasing sequence 
$(\mathcal{A}_n)$ of partitions of $T$ is called {\sl admissible} if
for all $n=0,1,2,\ldots,$  $\#\mathcal{A}_n \le 2^{2^n}$. 
For any $t\in T$, denote by $A_n(t)$ the unique element 
of $\mathcal{A}_n$ that contains $t$.
Let $\Delta(A)$ denote the diameter of the set $A\subset T$.
Define, for $\beta =1,2$,
\[
\gamma_{\beta}(T,d)
  =\inf_{\mathcal{A}_n}\sup_{t \in T} \sum_{n \ge 0} 2^{n/\beta}\Delta(A_n(t))~,
\]
% \emi{I have changed the \alpha into a \beta in the previous definition of gamma.}
where the infimum is taken over all admissible sequences.
Then one has
\begin{equation}
\label{eq:classical}
  \EXP m_{\text{ERM}}-m^* 
\le \frac{c}{\sqrt{n}}\EXP \gamma_2(\F,d_{\mathbb{X}}) \,,
\end{equation}
for some universal constant $c$. This bound implies
(\ref{eq:dudley1}) as 
$\gamma_2(\F,d_{\mathbb{X}})$ is bounded by a constant multiple of
the entropy integral 
$\int_0^1 \sqrt{\log N_{\mathbb{X}}(\F,\epsilon)}d\epsilon$ (see, e.g., \cite{talagrand}).


However, when the functions $f$ are no longer uniformly bounded and
the random variables $f(X)$ may have a heavy tail, 
empirical risk minimization may have a much poorer performance.
This is simply due to the fact that empirical averages become
poor estimates of expected values. Indeed, for heavy-tailed distributions,
several estimators of the mean are known to outperform simple empirical 
averages. It is a natural idea to define 
a robust version of empirical risk minimization based on minimizing 
such robust estimators. 

In this paper we focus on an elegant and powerful estimator
proposed and analyzed by Catoni \cite{Cat10}. (A version of) 
Catoni's estimator may be defined as follows.

Introduce the non-decreasing differentiable {\sl truncation function}
\begin{equation}
\label{eq:trunc}
 \phi (x) = -\IND{x<0}\log\left(1-x+\frac{x^2}{2}\right) +\IND{x\ge 0}\log\left(1+x+\frac{x^2}{2}\right)~.
\end{equation}
To estimate $m_f=\EXP f(X)$ for some $f\in \F$, define, for 
all $\mu \in \R$,
\[
\wh{r}_f(\mu) = \frac{1}{n\alpha} \sum_{i=1}^n\phi (\alpha(f(X_i)-\mu))
\]
where $\alpha>0$ is a parameter of the estimator to be specified below.
Catoni's estimator of $m_f$ is defined as the
unique value  $\wh{\mu}_f$ for which
$\wh{r}_f (\wh{\mu}_f)=0$. 
(Uniqueness is ensured by the strict monotonicity of $ \mu \mapsto \wh{r}_f(\mu) $).
Catoni proves that for any fixed $f\in \F$ and $\delta \in [0,1]$
such that $n>2\log(1/\delta)$, under the only 
assumption that $\var{f(X)} \le v$, the estimator above with
\[
  \alpha = \sqrt{\frac{2\log(1/\delta)}
  {n\left(v+\frac{2v\log(1/\delta)}{n(1-(2/n)\log(1/\delta))}\right)}}
\]
satisfies that, with probability at least $1-2\delta$,
\begin{equation}
\label{eq:catoni0}
  \left|m_f-\wh{\mu}_f\right| \le \sqrt{\frac{2v\log(1/\delta)}{n(1-(2/n)\log(1/\delta))}}~.
\end {equation}
In other words, the deviations of the estimate exhibit a sub-Gaussian
behavior. The price to pay is that the estimator depends both on
the upper bound $v$ for the variance and on  
the prescribed confidence $\delta$ via the parameter $\alpha$.
%Also note that Catoni's bound does not say anything about
%the expected deviation $\EXP   \left|m_f-\wh{\mu}_f\right|$.

Catoni also shows that for any $n>4(1+\log(1/\delta))$, if
$\var{f(X)} \le v$, the choice
\[
  \alpha = \sqrt{\frac{2}{nv}}
\]
guarantees that, with probability at least $1-2\delta$,
\begin{equation}
\label{eq:catoni}
\left|m_f-\wh{\mu}_f\right| 
   \le \left(1+\log(1/\delta)\right)\sqrt{\frac{v}{n}}~.
\end {equation}
Even though we lose the sub-Gaussian tail behavior, the estimator
is independent of the required confidence level.

Given such a powerful mean estimator, it is natural to propose 
an empirical risk minimizer that
selects a function from the class $\F$ that minimizes Catoni's
mean estimator. 
Formally, define
\[
\wh{f}=\underset{f \in \F}{\text{argmin}}\ \wh{\mu}_f
\]
where again, for the sake of simplicity we assume that the minimizer
exists. (Otherwise one may select an appropriate approximate minimizer
and all arguments go through in a trivial way.)

Once again, as a first step of understanding the excess risk
$m_{\wh{f}}-m^*$, we may use the simple bound
\[
    m_{\wh{f}}-m^* = \left(m_{\wh{f}}- \wh{\mu}_{\wh{f}}\right) 
     + \left( \wh{\mu}_{\wh{f}}-   m^* \right)
\le 2\sup_{f\in \F} \left| m_f-\wh{\mu}_f\right|~.
\]
When $\F$ is a finite class of cardinality, say $|\F|=N$, 
Catoni's bound may be combined, in a straightforward way, 
with the union-of-events bound. Indeed, if the estimators $\wh{\mu}_f$
are defined with parameter
\[
  \alpha = \sqrt{\frac{2\log(N/\delta)}
  {n\left(v+\frac{2v\log(N/\delta)}{n(1-(2/n)\log(N/\delta))}\right)}}~,
\]
then, with probability at least $1-2\delta$,
\[
\sup_{f\in \F}  \left|m_f-\wh{\mu}_f\right| 
\le \sqrt{\frac{2v\log(N/\delta)}{n(1-(2/n)\log(N/\delta))}}~.
\]
Note that this bound requires that $\sup_{f\in \F} \var{f(X)} \le v$,
that is, the variances are uniformly bounded by a {\sl known} value $v$.
Throughout the paper we work with this assumption.
However, this bound does not take into account the structure of the
class $\F$ and it is useless when $\F$ is an infinite class.
Our strategy to obtain meaningful bounds is to use
{\sl chaining} arguments. However, the extension is nontrivial and
the argument becomes more involved. The main results of the
paper present performance bounds for empirical minimization
of Catoni's estimator based on generic chaining.

\remark {\sc (median-of-means estimator.)} 
Catoni's estimator is not the only one with sub-Gaussian deviations
for heavy-tailed distributions. Indeed, the {\sl median-of-means} estimator,
proposed by Nemirovsky and Yudin \cite{NeYu83} (and also independently by
Alon, Matias, and Szegedy \cite{AMS02}) has similar performance guarantees 
as (\ref{eq:catoni0}). This estimate is obtained by dividing the
data in several small blocks, calculating the sample mean within 
each block, and then taking the median of these means. 
Hsu and Sabato \cite{HsuSa13} and Minsker \cite{Min13} 
introduce multivariate generalizations of the median-of-means 
estimator and use it to define and analyze certain statistical
learning procedures in the presence of heavy-tailed data. 
The sub-Gaussian behavior is 
achieved under various assumptions on the 
loss function. 
Such conditions can be avoided here. 
As an example, we detail applications of our results in Section \ref{sec:apps} for three different examples of loss functions.
An important advantage of the median-of-means estimate over Catoni's estimate is that 
the parameter of the estimate (i.e., the number of blocks) only depends
on the confidence level $\delta$ but not on $v$ and therefore no prior
upper bound of the variance $v$ is required to compute this estimate.
Also, the median-of-means estimate is useful even when the variance
is infinite and only a moment of order $1+\epsilon$ exists for some
$\epsilon >0$ (see Bubeck, Cesa-Bianchi, and Lugosi \cite{BuCeLu13}).  
Lerasle and Oliveira \cite{LeOl12} consider 
empirical minimization of the median-of-means
estimator and obtain interesting results in various statistical
learning problems.
However, to establish 
metric-entropy bounds for minimization of this mean estimate
remains to be a challenge. 

%G Not true:
%% \remark {\sc (computation.)} 
%% An important feature of empirical minimization based on Catoni's 
%% estimate is that the minimizer can be computed efficiently in many cases.
%% Indeed, if $\Phi:\R\to \R$ denotes a 
%% strictly convex differentiable function such that $\Phi'=\phi$ then 
%% Catoni's estimator equals
%% \[
%% \wh{\mu}_f
%%   = \argmin_{\mu} \frac{1}{n\alpha} \sum_{i=1}^n\Phi (\alpha(f(X_i)-\mu))~.
%% \]
%% Thus, when the class $\F$ is convex, finding the minimum of
%% $\wh{\mu}_f$ over $f\in \F$ is equivalent to minimizing the convex
%% function
%% \[
%%   h(f,\mu)= \frac{1}{n\alpha} \sum_{i=1}^n\Phi (\alpha(f(X_i)-\mu))
%% \]
%% in $f$ and $\mu$ which is 
%% a convex optimization problem for the pair $(f,\mu)\in \F\times \R$.
%% Such convex optimization problems may be solved efficiently in many
%% interesting cases. 

The rest of the paper is organized as follows. In Section \ref{sec:results}
we state and discuss the main results of the paper. Section \ref{sec:proofs}
is dedicated to the proofs. 
In Section \ref{sec:apps} we describe some applications
to regression under the absolute and squared losses and $k$-means
clustering.
Finally, in Section \ref{sec:sim} we present some simulation results both for
regression and $k$-means clustering.
The simulation study gives empirical evidence that the proposed
empirical risk minimization procedure improves performance in a
significant manner in the presence of heavy-tailed data. 
Some of the more technical arguments are relegated to the Appendix.


\section{Main results}
\label{sec:results}


The bounds we establish for the excess risk
depend on the geometric structure of the
class $\F$ under different distances. The $L_2(P)$ distance 
is defined, for $f,f'\in \F$, by
\[
d(f,f')=\left(\EXP\left[\left(f(X)-f'(X)\right)^2\right]\right)^{1/2}
\] 
and the $L_{\infty}$ distance is
\[ 
D(f,f') = \sup_{x\in \X}\left|f(x)-f'(x)\right|~.
\]
We also work with the (random) empirical quadratic distance 
\[
d_{\mathbb{X}}(f,f') = \left(\frac{1}{n}\sum_{i=1}^n (f(X_i)-f'(X_i))^2\right)^{1/2}~.
\]
Denote by $f^*$ a function with minimal expectation
\begin{eqnarray*}
f^*=\underset{f \in \F}{\text{argmin}}\ m_f~.
\end{eqnarray*}

Next we present two results that bound the excess risk
$m_{\hf}-m_{f^*}$ of the minimizer $\hf$ of Catoni's risk estimate in terms of metric properties of the class $\F$.
The first result involves a combination of terms involving the $\gamma_2$
and $\gamma_1$
functionals under the metrics $d$ and $D$ while the second is in terms
of quantiles of $\gamma_2$ under the empirical metric $d_{\mathbb{X}}$.

%\emi{In the two theorems the constant L and K are now just universal constants.}
\begin{theorem}
\label{thm:main}
Let $\F$ be a class of non-negative functions defined on
a set $\X$ and let $X,X_1,\ldots,X_n$ be i.i.d.\ random 
variables taking values in $\X$.
Assume that there exists $v>0$
such that $\sup_{f\in \F} \var{f(X)}\le  v$. 
Let $\delta \in (0,1/3)$.
Suppose that $\wh{f}$ is selected from $\F$ by minimizing Catoni's
mean estimator with parameter $\alpha$. 
Then there exists a universal constant $L$ such that, under the condition
\[
6\left(\alpha v+\frac{2\log (\delta^{-1})}{n\alpha}\right)+ L\log(2\delta^{-1})\left(\frac{\gamma_2(\F,d)}{\sqrt{n}} 
+\frac{\gamma_1(\F,D)}{n} \right) \le \frac{1}{\alpha}~,
\]
% \emi{I added the condition and erased the alpha large} 
with probability at least $1-3\delta$, the risk of $\wh{f}$
satisfies
\[
m_{\hf}-m_{f^*} \le 6\left(\alpha v+\frac{2\log (\delta^{-1})}{n\alpha}\right)+L\log(2\delta^{-1})\left(\frac{\gamma_2(\F,d)}{\sqrt{n}} 
+\frac{\gamma_1(\F,D)}{n} \right)~.
\]
\end{theorem}

\begin{theorem}
\label{thm:alternative}
Assume the hypotheses of Theorem \ref{thm:main}. We denote by $ \text{diam}_d(\F) $ the diameter of the class $\F$ under the distance $d$.
Set $ \Gamma_{\delta} $ such that $ \prob{\gamma_2(\F,d_{\mathbb{X}}) > \Gamma_{\delta}} \le \frac{\delta}{8}$. Then there exists a universal constant $K$ such that, under the condition
\[
6\left(\alpha v+\frac{2\log (\delta^{-1})}{n\alpha}\right)+ K\max(\Gamma_{\delta},\text{diam}_d(\F))\sqrt{\frac{\log (\frac{8}{\delta})}{n}} \le \frac{1}{\alpha}~,
\]
% \emi{Same thing here} 
with probability at least $1-3\delta$, the risk of $\wh{f}$
satisfies
\[
m_{\hf}-m_{f^*} \le 6\left(\alpha v+\frac{2\log (\delta^{-1})}{n\alpha}\right)+K\max(\Gamma_{\delta},\text{diam}_d(\F))\sqrt{\frac{\log (\frac{8}{\delta})}{n}}~.
\]
\end{theorem}
In both theorems above, the choice of $\alpha$ only influences the term $\alpha v+2\log (\delta^{-1})/(n\alpha)$. By taking
$\alpha=\sqrt{2\log (\delta^{-1})/(nv)}$, this term equals
\[
2\sqrt{\frac{2v\log (\delta^{-1})}{n}}~.
\]
For example, in that case, the condition in Theorem \ref{thm:main} reduces to
\[
12\sqrt{\frac{2v\log (\delta^{-1})}{n}}+L\log(\delta^{-1})\left(\frac{\gamma_2(\F,d)}{\sqrt{n}} 
+\frac{\gamma_1(\F,D)}{n} \right) \le \sqrt{\frac{nv}{2\log (\delta^{-1})}}~.
\]
This holds for sufficiently large values of $n$.
%\emi{Added a comment on the choice of \alpha}
This choice has the disadvantage that the estimator depends on the confidence level (i.e., on the value of $\delta$).
By taking $\alpha=\sqrt{2/(nv)}$, independently of $\delta$, one obtains the slightly worse term
\[
\sqrt{\frac{2v}{n}}(1+\log (\delta^{-1}))~.
\]
%\emi{I erased the sentence : In those two cases, $\alpha \underset{n\to +\infty}{\longrightarrow} 0$ which validates the hypothesis of the theorems.}
Observe that the main term in the second part of the bound of Theorem \ref{thm:main} is 
\[
L\log(\delta^{-1})\frac{\gamma_2(\F,d)}{\sqrt{n}}
\]
which is comparable to the bound (\ref{eq:classical}) obtained under 
the strong condition of $f(X)$ being uniformly bounded. 
All other terms are of smaller order.
Note that 
this part of the bound depends on the ``weak'' distribution-dependent
$L_2(P)$ metric $d$. The quantity $\gamma_1(\F,D) \ge \gamma_2(\F,d)$ also enters the
bound of Theorem \ref{thm:main} though only multiplied by $1/n$. The presence of this term 
requires that $\F$ be bounded in the $L_{\infty}$ distance $D$ which 
limits the usefulness of the bound. 
In Section  \ref{sec:apps} we illustrate the bounds on two applications
to regression and $k$-means clustering. In these applications, in spite
of the presence of heavy tails, the covering numbers under the distance $D$
may be bounded in a meaningful way.
Note that no such bound can hold
for ``ordinary'' empirical risk minimization that minimizes the
usual empirical means $(1/n)\sum_{i=1}^n f(X_i)$ because of the
poor performance of empirical averages in the presence of heavy 
tails. 

The main merit of the bound of Theorem \ref{thm:alternative} is that it
does not require that the class $\F$ has a finite diameter under the
supremum norm. Instead, the quantiles of $\gamma_2(\F,d_{\mathbb{X}})$ 
enter the picture. In Section  \ref{sec:apps} we show through
the example of $L_2$ regression how these quantiles may be estimated.



\section{Proofs}
\label{sec:proofs}

The proofs of Theorems \ref{thm:main} and \ref{thm:alternative} 
are based on showing that the excess risk can be bounded as soon
as the supremum of the empirical process
$\{X_f(\mu): f\in\F\}$ is bounded for any
fixed $\mu\in\R$, where for any $f\in \F$ and $\mu\in\R$, we define
$X_f(\mu)=\hr_f(\mu)-\br_f(\mu)$ with
\[
  \ol{r}_f (\mu) = \frac{1}{\alpha} \esp{\phi (\alpha(f(X)-\mu))}
\]
and
\[
\wh{r}_f(\mu) = \frac{1}{n\alpha} \sum_{i=1}^n\phi (\alpha(f(X_i)-\mu))~.
\]
The two theorems differ in the way the supremum of this empirical process is bounded.


%Note first that, by the definition of Catoni's estimator,
%$\wh{\mu}_f\ge \inf_{i} f(X_i)$. In particular, $\wh{\mu}_f\ge 0$
%for all $f\in\F$. 
Let $A_{\alpha}(\delta)=\alpha v+2\log (\delta^{-1})/(n\alpha)$.

Once again, we may assume, essentially without loss of generality, that the
minimum exists. In case of multiple minimizers we may choose one 
arbitrarily. 
The main result in \cite{Cat10} states that for any $\delta>0$ such that 
$\alpha^2v + 2\log (\delta^{-1})/n \le 1$,
with probability at least $1-2\delta$,
\begin{equation}
\label{eq-cat}
\left|\wh{\mu}_{f^*}- m_{f^*}\right| \le A_{\alpha}(\delta)~.
\end{equation}
%\emi{This is the new location of the definition of $\Omega_{f^*}(\delta) $. }
Let $\Omega_{f^*}(\delta) $ be the event on which inequality (\ref{eq-cat}) holds. By definition, $\prob{\Omega_{f^*}(\delta)} \ge 1-2\delta$.

\subsection{A deterministic version of $\wh{\mu}_f$}
We begin with a variant of the argument of Catoni \cite{Cat10}. 
It involves a deterministic version $\ol{\mu}_f$ of the estimator defined,
for each $f\in \F$, as the unique solution of the equation
$\ol{r}_f (\mu) = 0$.

In Lemma \ref{lem:br} below we show that $\ol{\mu}_f$ is 
in a small (deterministic) interval centered at $m_f$.   
For any $f\in \F$, $\mu\in\R$, and $\ep\ge 0$, define
\begin{eqnarray*}
B_f^+(\mu,\ep)=(m_f-\mu)+\frac{\alpha}{2}(m_f-\mu)^2+\frac{\alpha}{2}v+\ep~, \\
B_f^-(\mu,\ep)=(m_f-\mu)-\frac{\alpha}{2}(m_f-\mu)^2-\frac{\alpha}{2}v-\ep
\end{eqnarray*}
and let
\[
\mu_f^+(\ep)=m_f+\alpha v+2\ep~, \qquad
\mu_f^-(\ep)=m_f-\alpha v-2\ep~.
\]
As a function of $\mu$, $B_f^+(\mu,\ep)$ is a quadratic polynomial such that $\mu_f^+(\ep)$ is an upper bound of the smallest root of $B_f^+(\mu,\ep)$. Similarly, $\mu_f^-(\ep)$ is a lower bound of the largest root of $B_f^-(\mu,\ep)$. Implicitly we assumed that these roots always exist. This is not always the case but a simple condition on $\alpha$ guarantees that these roots exists.
In particular, 
$ 1-\alpha^2v-2\alpha\ep\ge 0 $ guarantees that $ B_f^+(\mu,\ep)=0 $ and $ B_f^-(\mu,\ep)=0 $  have at least one solution. This condition will always
be satisfied by our choice of $\epsilon$ and $\alpha$.

 %% $\ep$ can be seen as the error made compared to the complete deterministic case. As we will see below, for Catoni's estimator this error is given by $ \frac{\log \delta^{-1}}{n\alpha} $ and by $0$ for the deterministic quantity $\ol{r}_f(\mu)$.
 
%\emi{I deleted the following proposition} 
 
%In our notation, Proposition 2.2 in \cite{Cat10} is equivalent to the following.
%\begin{prop}
%\label{prop-cat}
%Let $\delta >0$ and $\mu \in \R$. For any $f\in \F$, the events 
%\begin{eqnarray*}
%\Omega_{f}^-(\mu,\delta)&=&\left\{ B_f^-\left(\mu,\frac{\log \delta^{-1}}{n\alpha}\right)\le \hr_f(\mu)\right\}\\
%\Omega_{f}^+(\mu,\delta)&=&\left\{ \hr_f(\mu) \le B_f^+\left(\mu,\frac{\log \delta^{-1}}{n\alpha}\right)\right\}
%\end{eqnarray*}
%both hold with probability at least $1-\delta$.
%\end{prop}
%
%
%Let $\ep=\frac{\log \delta^{-1}}{n\alpha}$ and define
%\[
%\Omega_{f^*}(\delta)\overset{\text{def}}{=}\Omega_{f}^-(\mu^-_{f^*}(\ep),\delta)\ \cap\  \Omega_{f}^+(\mu^+_{f^*}(\ep),\delta)~.
%\]
%If $\alpha^2v +\frac{2\log \delta^{-1}}{n} \le 1$, (\ref{eq-cat}) holds on the event $\Omega_{f^*}(\delta)$. (Just replace $\ep$ by $\frac{\log \delta^{-1}}{n\alpha}$ in the expression of $\mu^+_{f^*}(\ep)$ and $\mu^-_{f^*}(\ep)$.) 
%Since $\wh{\mu}_{f^*}$ is the unique zero of $ \wh{r}_{f^*}(\mu) $, it is squeezed into the interval $ [\mu^-_{f^*}(\ep)\ ,\ \mu^+_{f^*}(\ep)] $ centered at $m_{f^*}$ and of size $2A_{\alpha}(\delta)$. Note that $\prob{\Omega_{f^*}(\delta)} \ge 1-2\delta$.

Still following the ideas of \cite{Cat10}, the next lemma bounds $\ol{r}_f (\mu)$ 
by the quadratic polynomials $B^+$ and $B^-$. The lemma will help us compare the zero of $\ol{r}_f (\mu)$ to the zeros of these quadratic functions.
\begin{lem}
\label{lem:br}
For any fixed $f\in \F$ and $\mu \in \R$,
\begin{equation}
\label{eq-det}
B_f^-(\mu,0)\le \br_f(\mu) \le B_f^+(\mu,0)~,
\end{equation}
and therefore $m_f-\alpha v\le \ol{\mu}_f \le m_f+\alpha v$.
In particular,
\[
\label{eq-br}
B_{\hf}^-(\mu,0)\le \br_{\hf}(\mu) \le B_{\hf}^+(\mu,0)~.
\]
For any $\mu$ and $\ep$ such that $\br_{\hf}(\mu) \le \ep$, if $ 1-\alpha^2v-2\alpha\ep\ge 0 $, then 
\begin{equation}
\label{eq-mf}
m_{\hf} \le \mu +\alpha v+ 2\ep~.
\end{equation}
\end{lem}
\begin{proof}
\begin{figure}
\label{fig_B_f}
\caption{Representation of $ \br_f(\mu) $ and the quadratic functions $ B_f^-(\mu,0)$ and $B_f^+(\mu,0)$.}
\includegraphics[scale=0.6]{Erm-shema2.eps}\\
$ \br_f(\mu)  $ is squeezed between $ B_f^-(\mu,0)$ and $B_f^+(\mu,0)
$. In particular at $ \mu^+_f(0) $ (resp. $ \mu^-_f(0)$), $\br_f(\mu)$
is non-positive (resp. non-negative). Any $\mu$ such that $\br_f(\mu) \le \ep$ is above $\mu_f^{-}(\ep)$.
\end{figure}
%\emi{Added the figure to explain the proof.}
Writing  $Y$ for $\alpha (f(X)-\mu)$ and using the fact that
$\phi(x)\le \log(1+x+x^2/2)$ for all $x\in \R$, 
\begin{eqnarray*} 
\exp\left(\alpha \ol{r}_f (\mu) \right)  
& \le  & \exp \left( \EXP\left[\log (1+Y+\frac{Y^2}{2})\right]\right)\\
& \le  & \EXP\left[1+Y+\frac{Y^2}{2}\right]\\
& \le & 1+\alpha (m_f-\mu ) + \frac{\alpha^2}{2}\left[v+(m_f-\mu)^2\right] \\
& \le  & \exp \left(\alpha B_f^+ (\mu,0)\right)~.
\end{eqnarray*}
Thus, we have $\ol{r}_f (\mu) -  B_f^+(\mu,0) \le 0$ (see Figure
\ref{fig_B_f}). Since this last inequality is true for any $f$,
$\sup_f(\ol{r}_{f} (\mu) -  B_{f}^+(\mu,0)) \le 0$ and the second
inequality of (\ref{eq-det}) is proved. The second statement of the
lemma may be proved by a similar argument.

If $\br_{\hf}(\mu) \le \ep$ then $B_{\hf}^-(\mu,0)\le \ep$ which is equivalent to $B_{\hf}^-(\mu,\ep)\le 0$. If $ 1-\alpha^2v-2\alpha\ep\ge 0 $ then a solution of $B_{\hf}^-(\mu,\ep)= 0$ exists and since $\br_{\hf}(\mu)$ is a non-increasing function, $\mu$ is above the largest of these two solutions. This implies $\mu^{-}_{\hf}(\ep)\le \mu$ which gives inequality ($\ref{eq-mf}$) (see Figure \ref{fig_B_f}).
\end{proof}
Inequality (\ref{eq-mf}) is the key tool to ensure that the risk $m_{\hf}$ of the minimizer $\hf$ can be upper bounded as soon as $\bar{r}_{\hf}$ is. 
It remains to find the smallest $\mu$ and $\ep$ such that $\bar{r}_{f}(\mu)$ is bounded uniformly on $\F$.


\subsection{Bounding the excess risk in terms of the supremum of an empirical process}


%% The last remaining challenge remains to choose a $\mu_0$ where we will use Theorem \ref{thm-controlr_f} and then to show that $\ol{r}_{\hf}(\mu_0)$ is small enough at this chosen point. The last step will be given by equation (\ref{eq-mf}) for this $\mu_0$ cleverly chosen. The ideal choice would be $\mu_0=\wh{\mu}_{\hf}$. Nevertheless, we recall that any choice of $\mu_0$ depending on the data won't allow us to use Theorem \ref{thm-controlr_f}. We will then use the best known deterministic upper bound for $\wh{\mu}_{\hf}$ on the event $ \Omega_{f^*}(\delta) $: 

The key to all proofs is that we link the excess risk to the supremum of the 
empirical process $X_f(\mu)=\hr_f(\mu)-\br_f(\mu)$ as $f$ ranges through $\F$ for a suitably
chosen value of $\mu$. For fixed $\mu\in \R$ and $\delta\in (0,1)$, 
define the $1-\delta$ quantile of $\sup_{f\in \F}|X_f(\mu)-X_{f^*}(\mu)|$
by $Q(\mu,\delta)$, that is, the infimum of all positive
numbers $q$ such that
\[
  \PROB\left\{\sup_{f\in \F}|X_f(\mu)-X_{f^*}(\mu)| \le q \right\}
   \ge 1-\delta~.
\]
First we need a few simple facts summarized in the next lemma.
\begin{lem} 
\label{lem:mu0}
Let $\mu_0=m_{f^*}+A_{\alpha}(\delta)$. Then on the event $\Omega_{f^*}(\delta)$, the following inequalities hold:
\begin{enumerate}
\item $ \hr_{\hf}(\mu_0)\le 0 $
\item $\br_{f^*}(\mu_0) \le 0$
\item $-\hr_{f^*}(\mu_0) \le 2A_{\alpha}(\delta)$
\end{enumerate}
\end{lem}
\begin{proof}
We prove each inequality separately.
\begin{enumerate}
\item First note that on $ \Omega_{f^*}(\delta)$  inequality (\ref{eq-cat}) holds and 
we have $\wh{\mu}_{\hf} \le \wh{\mu}_{f^*}\le \mu_0 $. Since $\hr_{\hf}$ is a non-increasing function of $\mu$, 
$\hr_{\hf}(\mu_0)\le \hr_{\hf}(\wh{\mu}_{\hf})=0$.
%\emi{The previous item is clearer}
\item By (\ref{eq-det}), $\wb{\mu}_{f^*} \le m_{f^*}+\alpha v\le m_{f^*}+\alpha v +2\log (\delta^{-1})/(n \alpha)=\mu_0$. Since $\br_{f^*} $ is a non-increasing function, $\br_{f^*}(\mu_0) \le \br_{f^*}(\wb{\mu}_{f^*}) = 0$.
\item $\hr_{f^*}$ is a $1$-Lipschitz function and therefore
\begin{eqnarray*}
|\hr_{f^*}(\mu_0)|=|\hr_{f^*}(\wh{\mu}_{f^*})-\hr_{f^*}(\mu_0)|&\le& |\wh{\mu}_{f^*}-\mu_0|\\
&\le&|\wh{\mu}_{f^*}-m_{f^*}|+|m_{f^*}-\mu_0|\\
&\le&2A_{\alpha}(\delta)
\end{eqnarray*}
which gives $-\hr_{f^*}(\mu_0) \le 2A_{\alpha}(\delta)$.
\end{enumerate}
\end{proof}

We will use Lemma \ref{lem:br} with $\mu_0$ introduced in Lemma \ref{lem:mu0}. Recall that $\prob{\Omega_{f^*}(\delta)} \ge 1-2\delta$.

With the notation introduced above, we see that with probability at least $1-\delta$,
\begin{eqnarray*}
\br_{\hf}(\mu_0) &\le& \hr_{\hf}(\mu_0)+\br_{f^*}(\mu_0)-\hr_{f^*}(\mu_0)+\left|\br_{\hf}(\mu_0)-\hr_{\hf}(\mu_0)-\br_{f^*}(\mu_0)+\hr_{f^*}(\mu_0)\right|\\
&\le& \hr_{\hf}(\mu_0)+\br_{f^*}(\mu_0)-\hr_{f^*}(\mu_0)+\sup_{f\in \F}\left|\br_{f}(\mu_0)-\hr_{f}(\mu_0)-\br_{f^*}(\mu_0)+\hr_{f^*}(\mu_0)\right|\\
&\le& \hr_{\hf}(\mu_0)+\br_{f^*}(\mu_0)-\hr_{f^*}(\mu_0) +Q(\mu_0,\delta)~.
\end{eqnarray*}
This inequality, together with Lemma \ref{lem:mu0}, implies that, with probability at least $1-3\delta$,
\[
\br_{\hf}(\mu_0) \le 2A_{\alpha}(\delta)+Q(\mu_0,\delta)~.
\]
Now using Lemma \ref{lem:br} with $ \ep = 2A_{\alpha}(\delta)+Q(\mu_0,\delta) $ and under the condition $ 1-\alpha^2v-4\alpha A_{\alpha}(\delta)-2\alpha Q(\mu_0,\delta) \ge 0 $, we have
\begin{eqnarray}
\label{eq:principal}
m_{\hf} - m_{f^*}&\le& \alpha v+5 A_{\alpha}(\delta)+2 Q(\mu_0,\delta) \nonumber \\
&\le& 6\left(\alpha v +\frac{2\log (\delta^{-1})}{n \alpha}\right) + 2 Q(\mu_0,\delta)~,
\end{eqnarray} 
with probability at least $1-3\delta$.
The condition $ 1-\alpha^2v-4\alpha A_{\alpha}(\delta)-2\alpha
Q(\mu_0,\delta) \ge 0$ is satisfied whenever
\[
6\left(\alpha v +\frac{2\log (\delta^{-1})}{n \alpha}\right)+2 Q(\mu_0,\delta) \le \frac{1}{\alpha}
\]
holds.
%\emi{I changed a little the form of the condition in order to fit the bound of Theorem 1 and 2}


\subsection{Bounding the supremum of the empirical process}
\label{subsec:chain}

Theorems \ref{thm:main} and \ref{thm:alternative} both follow 
from (\ref{eq:principal}) by two different ways of bounding the quantile
$Q(\mu,\delta)$ of $\sup_{f\in \F}|X_f(\mu)-X_{f^*}(\mu)|$. 
Here we present these two inequalities. Both of them use
basic results of ``generic chaining'', see Talagrand \cite{talagrand}.
Theorem \ref{thm:main} follows from  (\ref{eq:principal}) and the 
next inequality:

\begin{prop}
\label{prop-controlr_f}
Let $\mu \in \R$ and $\alpha>0$. There exists a universal constant $L$ such that for any $\delta\in (0,1)$, 
\[
Q(\mu,\delta)
\le L\log(2\delta^{-1})\left(\frac{\gamma_2(\F,d)}{\sqrt{n}} 
+\frac{\gamma_1(\F,D)}{n} \right)~.
\]
\end{prop}

The proof is an immediate consequence of Theorem \ref{thm:chaining} and (\ref{eq-orlic}) in the 
Appendix and the following lemma.


\begin{lemma}
\label{lem-concentration1}
For any $\mu \in \R$, $ \alpha >0 $,
$f,f' \in \F$, and $t>0$,
$$ \prob{|X_f(\mu)-X_{f'}(\mu)|>t} \le 2\exp \left(-\frac{nt^2}{2(d(f,f')^2+\frac{2D(f,f')t}{3})}\right) $$
where the distances $d,D$ are defined at the beginning of Section \ref{sec:results}.
\end{lemma}
% \emi{The 2 is no longer missing in previous Lemma}
\begin{proof}
Observe that $n(X_f(\mu)- X_{f'}(\mu))$ is the sum of the independent zero-mean
random variables
\begin{eqnarray*}
 C_i(f,f') &  = & \frac{1}{\alpha}\phi
 (\alpha(f(X_i)-\mu))-\frac{1}{\alpha}\phi (\alpha(f'(X_i)-\mu))  \\
& & -\left[\frac{1}{\alpha}\esp{\phi (\alpha(f(X)-\mu))}-\frac{1}{\alpha}\esp{\phi (\alpha(f'(X)-\mu))}\right]~.
\end{eqnarray*}
Note that since the truncation function $\phi$ is 1-Lipschitz, we have
$C_i(f,f')\leq 2D (f,f') $. Also,
\[
 \sum_{i=1}^{n} \EXP[C_i(f,f')^2] \leq \sum_{i=1}^{n}\EXP\left[\left((f(X_i)-\mu)-(f'(X_i)-\mu)\right)^2\right]=n d(f,f')^2
\]
The lemma follows from Bernstein's inequality (see, e.g., \cite[Equation (2.10)]{gabor}).
% \emiQ{Here I replaced the reference Theorem 2.10 by Equation 2.10 since this is really what we use.}
\end{proof}

Similarly, Theorem \ref{thm:alternative} is implied by (\ref{eq:principal}) and
the following. Recall the notation of Theorem \ref{thm:alternative}.

\begin{thm}
Let $\mu \in \R$, $\alpha>0$, and $\delta\in (0,1/3)$.
There exists a universal constant $K$ such that
\[
Q(\mu,\delta)
\le K\max(\Gamma_{\delta},\text{diam}_d(\F))\sqrt{\frac{\log (\frac{8}{\delta})}{n}} ~.
\]

\end{thm}
%\emi{I changed the proof of this theorem entirely}

\begin{proof}
Assume $ \Gamma_{\delta} \ge \text{diam}_d(\F) $. The proof is based on a standard symmetrization argument.
Let $(X'_1,\dots,X'_n)$ be independent copies of $(X_1,\dots,X_n)$ and
define
\[
Z_i(f)= \frac{1}{n\alpha}\phi(\alpha(f(X_i)-\mu))-\frac{1}{n\alpha}\phi(\alpha(f(X'_i)-\mu))~.
\]
Introduce also independent Rademacher random variables
$(\ep_1,\dots,\ep_n)$.  For any $f\in \F$, denote  by $Z(f) = \sum_{i=1}^{n}\ep_iZ_i(f)$. Then by Hoeffding's inequality, for
all
$f,g \in \F$ and for every $t>0$,
\begin{equation}
\label{eq:hoeffding}
 \probi{(\ep_1,\dots,\ep_n)}{|Z(f)-Z(g)|>t} \le 2\exp \left(-\frac{t^2}{2d_{\mathbb{X},\mathbb{X}'}(f,g)^2}\right) 
\end{equation}
where 
$\PROB_{(\ep_1,\dots,\ep_n)}$ denotes probability with respect to the 
Rademacher variables only (i.e., conditional on the $X_i$ and $X_i'$)
and
$d_{\mathbb{X},\mathbb{X}'}(f,g) = \sqrt{\sum_{i=1}^n(Z_i(f)-Z_i(g))^2}$ is a random distance.
Using (\ref{eq:charac}) in the Appendix with distance $ d_{\mathbb{X},\mathbb{X}'} $ and (\ref{eq:hoeffding}),
we get that, for all $\lambda>0$,
\begin{equation}
\label{eq:subgauss}
\espi{(\ep_1,\dots,\ep_n)}{\exp\left(\lambda \sup_{f\in \F}\left|\sum_{i=1}^n \ep_i[Z_i(f)-Z_i(f^*)]\right|\right)} \le 2\exp\left(\lambda^2 L^2 \gamma_2(\F,d_{\mathbb{X},\mathbb{X}'})^2/4\right)
\end{equation}
where $L$ is a universal constant from Proposition \ref{cor:orlic}.
%Denote by $\hr'_f(\mu)$ the independent copy of $\hr_f(\mu)$ that depends only on the random vector $(X'_1,\dots,X'_n)$.
Observe that since $x \mapsto\phi( x)$ is Lipschitz with constant $1$,
\begin{eqnarray*}
\lefteqn{
d_{\mathbb{X},\mathbb{X}'}(f,g) } \\
&=&\left(\frac{1}{n^2\alpha^2}\sum_{i=1}^n
  \Big(\phi\big(\alpha(f(X_i)-\mu)\big)-\phi\big(\alpha(f(X'_i)-\mu)\big)
\right. \\ 
& & \left.  -\phi\big(\alpha(g(X_i)-\mu)\big)+\phi\big(\alpha(g(X'_i)-\mu)\big)\Big)^2\right)^{1/2}\\
&\le &\frac{1}{\sqrt{n}} \left(\frac{1}{n}\sum_{i=1}^n \Big(f(X_i)-g(X_i)\Big)^2\right)^{1/2}+\frac{1}{\sqrt{n}} \left(\frac{1}{n}\sum_{i=1}^n \Big(f(X'_i)-g(X'_i)\Big)^2\right)^{1/2}~.
\end{eqnarray*}
This implies
\[
\gamma_2(\F,d_{\mathbb{X},\mathbb{X}'}) \le \frac{1}{\sqrt{n}}\left(\gamma_2(\F,d_{\mathbb{X}})+\gamma_2(\F,d_{\mathbb{X}'})\right)~.
\]
Combining this with (\ref{eq:subgauss}), we obtain
\begin{eqnarray*}
\lefteqn{\prob{\sup_{f\in \F} \left|Z(f)-Z(f^*)\right| \ge t}}\\
& \le & \prob{\sup_{f\in \F} \left|Z(f)-Z(f^*)\right| \ge t\ \Big|\ \gamma_2(\F,d_{\mathbb{X}}) \le \Gamma_{\delta}\  \&\  \gamma_2(\F,d_{\mathbb{X}'})\le\Gamma_{\delta}}+2\prob{\gamma_2(\F,d_{\mathbb{X}}) > \Gamma_{\delta}} \\
&\le& \espi{\mathbb{X},\mathbb{X}'}{ \espi{(\ep_1,\dots,\ep_n)}{e^{\lambda \sup_{f\in
        \F}\left|\sum_{i=1}^n \ep_i[Z_i(f)-Z_i(f^*)]\right|}}\Big|\
  \gamma_2(\F,d_{\mathbb{X}}) \le \Gamma_{\delta}\  \&\
  \gamma_2(\F,d_{\mathbb{X}'})\le\Gamma_{\delta}}e^{-\lambda
  t}
\\ 
& &  +\frac{\delta}{4} 
\quad \text{(by the definition of $\Gamma_\delta$)} \\
&\le & 
2\exp \left(\frac{\lambda^2 L^2}{n} \Gamma_{\delta}^2-\lambda t\right)+\frac{\delta}{4}~.
\end{eqnarray*}
%Recall that, by definition, $ \Gamma_{\delta} $ is such that $ \prob{\gamma_2(T,d_{\mathbb{X}}) > \Gamma_{\delta}} \le \frac{\delta}{8}$. 
Optimization in $\lambda$ with $t= 2L\Gamma_{\delta}\sqrt{\log (8/\delta)/n}$ gives
\[
\prob{\sup_{f\in \F} \left|Z(f)-Z(f^*)\right| \ge t} \le \frac{\delta}{2}~.
\]
A standard symmetrization inequality of tail probabilities of
empirical processes (see, e.g., \cite[Lemma 3.3]{Geer00}) guarantees that 
\[
\prob{\sup_{f\in \F} \left|X_f(\mu)-X_{f^*}(\mu)\right| \ge 2t}\le 2\prob{\sup_{f\in \F} \left|Z(f)-Z(f^*)\right| \ge t}
\]
as long as for any $f \in \F$, $\prob{\left|X_f(\mu)-X_{f^*}(\mu)\right| \ge t}
\le \frac{1}{2}$. Recall that $X_f(\mu)-X_{f^*}(\mu)$ is a zero-mean random variable. Then by Chebyshev's inequality it suffices to have $ t \ge \sqrt{2}\text{diam}_d(\F)/\sqrt{n}$. Indeed,
\begin{eqnarray*}
\frac{\var{X_f(\mu)-X_{f'}(\mu)}}{t^2} & \le &
\frac{\var{\frac{1}{\alpha}\phi(\alpha(f(X)-\mu))-\frac{1}{\alpha}\phi(\alpha(f^*(X)-\mu))}}{nt^2}
\\
 &\le& \frac{\esp{(f(X)-f^*(X))^2}}{nt^2}\\
&\le & \frac{\text{diam}_d(\F)^2}{nt^2}~.
\end{eqnarray*}
Without loss of generality, we can assume $L \ge 1$. Since for any choice of $\delta <\frac{1}{3} $, $ \sqrt{\log (\frac{8}{\delta})} > \sqrt{2} $ we have $L\Gamma_{\delta}\sqrt{\log (\frac{8}{\delta})} \ge \text{diam}_d(\F) \sqrt{2}$. Thus 
\[
\prob{\sup_{f\in \F} \left|X_f(\mu)-X_{f^*}(\mu)\right| \ge 2L\Gamma_{\delta}\sqrt{\frac{\log (\frac{8}{\delta})}{n}}} \le \delta
\]
as desired. Now, if $\Gamma_{\delta} < \text{diam}_d(\F)$, $ \prob{\gamma_2(\F,d_{\mathbb{X}}) > \text{diam}_d(\F)} \le \frac{\delta}{8} $ and the same argument holds for $\text{diam}_d(\F)$ instead of $ \Gamma_{\delta} $. This concludes the proof.
%\emi{I've reworked the proof according to the report 2. It has been possible to erase a \sqrt{2} in one inequality}
\end{proof}





\section{Applications}
\label{sec:apps}

In this section we describe two applications of Theorems \ref{thm:main} and \ref{thm:alternative}
to simple statistical learning problems. The first is a regression estimation problem in which
we distinguish between $L_1$ and $L_2$ risks
and the second is $k$-means clustering.

\subsection{Empirical risk minimization for regression}

\subsubsection{$L_1$ regression}
\label{sec:L_1regr}
%\emi{The following sentence has been corrected.}
Let $(Z_1,Y_1),\ldots,(Z_n,Y_n)$ be independent identically distributed random variables
taking values in $\Z\times \R$ where $\Z$ is a bounded subset of (say) $\R^m$.
Suppose $\G$ is a class of functions $\Z \to \R$
bounded in the $L_{\infty}$ norm, that is, 
$\sup_{g\in \G} \sup_{z\in \Z}|g(z)|<\infty$. 
We denote by $\Delta$ the diameter of $\G$ under the distance induced by this norm.
%\emi{I changed how we present the hypothesis and the definition of \Delta}
First we consider the setup when
the {\sl risk} of each $g\in \G$ is defined by the $L_1$ loss
\[
  R(g) = \EXP |g(Z)-Y|
\]
where the pair $(Z,Y)$ has the same distribution of the $(Z_i,Y_i)$ 
and is independent of them. Let $g^*= \argmin_{g\in \G} R(g)$
be a minimizer of the risk (which, without loss of generality, 
is assumed to exist).
The statistical learning problem we consider here consists of choosing
a function $\wh{g}$ from the class $\G$ that has a risk $R(\wh{g})$
not much larger than $R(g^*)$.

The standard procedure is to pick $\wh{g}$ by minimizing the 
empirical risk $(1/n) \sum_{i=1} |g(Z_i)-Y_i|$ over $g\in \G$.
However, if the response variable $Y$ is unbounded and may have a heavy tail,
%\emi{minimization is may fail to provide => minimization may fail to provide}
ordinary empirical risk minimization may fail to provide a good predictor of $Y$ as 
the empirical risk is an unreliable estimate of the true risk.

Here we propose choosing $\wh{g}$ by minimizing Catoni's estimate.
To this end, we only need to assume that the second moment of $Y$
is bounded by a known constant. More precisely, assume that 
$\EXP Y^2 \le \sigma^2$ for some $\sigma>0$. Then 
$\sup_{g\in \G} \var{|g(Z)-Y|}\le 2\sigma^2 + 2\sup_{g\in \G} \sup_{z\in \Z}|g(z)|^2
\defeq v$ is a known and finite constant.
%\emi{I added the missing constant 2 in the previous definition of v}

Now for all $g\in \G$ and $\mu \in \R$, define
\[
\wh{r}_g(\mu) = \frac{1}{n\alpha} \sum_{i=1}^n\phi (\alpha(|g(X_i)-Y_i|-\mu))
\]
where $\phi$ is the truncation function
defined in (\ref{eq:trunc}). 
Define  $\wh{R}(g)$ as the unique value for which
$\wh{r}_g(\wh{R}(g))=0$. The empirical risk minimizer based on Catoni's
risk estimate is then
\[
  \wh{g}= \argmin_{g\in\G} \wh{R}(g)~.
\]
By Theorem \ref{thm:main}, the performance of $\wh{g}$ may be 
bounded in terms of covering numbers of the class of functions 
$\F=\{f(z,y)=|g(z)-y|: g\in \G\}$ based on the distance
\[
  D(f,f')=\sup_{z\in\Z,y\in\R} \left||g(z)-y|
  -|g'(z)-y| \right|
  \le \sup_{z\in\Z} \left|g(z) -g'(z) \right|~.
\]
Thus, the covering numbers of $\F$ under the distance $D$ may
be bounded in terms of the covering numbers of $\G$ under the
$L_{\infty}$ distance. Denoting by $N_{d}(A,\epsilon)$ the
$\epsilon$-covering
number of a set $A$ under the metric $d$,
we obtain the following:

\begin{cor}
Consider the setup described above. We assume $\int_0^\Delta \log N_{\infty}(\G,\epsilon)d\epsilon < \infty$. Let $n\in \N$, $\delta\in (0,1/3)$ and $\alpha=\sqrt{2\log (\delta^{-1})/(nv)}$. There exists an integer $N_0$ and a universal
constant $C$ such that, for all $n \ge N_0$, with probability
at least $1-3\delta$, 
\begin{eqnarray*}
   R(\wh{g}) - R(g^*) \le 12\sqrt{\frac{2v\log (\delta^{-1})}{n}}+
C\log (2\delta^{-1})\left(\frac{1}{\sqrt{n}}
 \int_0^\Delta \sqrt{\log N_{d}(\G,\epsilon)}d\epsilon+O\left(\frac{1}{n}\right)\right)~.
\end{eqnarray*}
\end{cor}

\begin{proof}
Clearly, if two distances $d_1$ and $d_2$ satisfy $d_1 \le d_2$, then
$ \gamma_1(\F,d_1)\le \gamma_1(\F,d_2) $. Thus, $  \gamma_1(\F,D) \le \gamma_1(\G,\norm{.}_{\infty}) \le L\int_0^\Delta \log N_{\infty}(\G,\epsilon)d\epsilon < \infty$ (see (\ref{eq:dudley})) and $\gamma_1(\F,D)/n = O\left(1/n\right) $. The condition
\[
12\sqrt{\frac{2v\log (\delta^{-1})}{n}}+
C\log (2\delta^{-1})\left(\frac{1}{\sqrt{n}}
 \int_0^\Delta \sqrt{\log N_{d}(\G,\epsilon)}d\epsilon+O\left(\frac{1}{n}\right)\right) \le \sqrt{\frac{nv}{2\log (\delta^{-1})}}
\]
is satisfied for sufficiently large $n$. 
Apply Theorem \ref{thm:main}. 
\end{proof}

Note that the bound essentially has the same form as
(\ref{eq:dudley1}) but to apply (\ref{eq:dudley1}) it is crucial 
that the response variable $Y$ is bounded or at least has 
sub-Gaussian tails. We get this under the weak assumption that 
$Y$ has a bounded second moment (with a known upper bound).
The price we pay is that covering numbers under the distance $d_{\mathbb{X}}$
are now replaced by covering numbers under the supremum norm.


%% \subsection{Support vector classification with the hinge loss}

%% In our second application we consider a classification problem
%% described as follows.
%% Let $(Z,Y),(Z_1,Y_1),\ldots,(Z_n,Y_n)$ be independent identically
%% taking values in $\R^m\times \{-1,1\}$. Suppose that there
%% exist $B>b>0$ such that $\PROB\{ \|Z\| > B\} = 0$ and 
%% $\left(\EXP \|Z\|^2\right)^{1/2} \le b$.
%% One is interested in finding a {\sl linear classifier}, that is, 
%% a unit vector $w\in S^{d-1}$ 
%% (where $S^{d-1}=\{w\in\R^m:\|w\|=1\})$ such that $\sgn(w^T Z)$ is
%% a good predictor of $Y$. Here we consider a stylized version of
%% {\sc svm} classifiers that chooses $\wh{w}$ by minimizing 
%% the sum of the {\sl hinge losses}  
%% \[
%%   \sum_{i=1}^n \left(c-Y_iw^TZ_i\right)_+
%% \]
%% where we take $c>0$ as a fixed parameter for simplicity of discussion.
%% For a thorough survey of the history, performance, and applications
%% of {\sc svm} classifiers we refer to \cite{StCh08}.

%% Suppose that the value of $b$ is known. (This is not an unrealistic assumption
%% as $b$ is easily estimated, for example, in the presence of unlabeled data.)
%% Then for all $w\in S^{d-1}$, 
%% $\var{\left(c-Yw^TZ\right)_+}\le 2(c^2+b^2)\defeq v$
%% one may replace minimization of the empirical hinge loss by
%% \[
%%   \wh{w}= \argmin_{w\in\R^d: \|w\|=1} \wh{R}(w)~,
%% \]
%% where
%%   $\wh{R}(w)$ is defined as the unique value for which
%% \[
%% \frac{1}{n\alpha} \sum_{i=1}^n\phi (\alpha(\left(c-Y_iw^TZ_i\right)_+-\wh{R}(g))) =0
%% \]
%% where $\alpha=\sqrt{2/(nv)}$ and $\phi$ is the truncation function
%% defined in (\ref{eq:trunc}). In order to use
%% Theorem \ref{thm:main} to bound the performance of $\wh{w}$, 
%% we estimate the covering numbers 
%% of the class $\F=\{f(z,y)=(c-yw^Tz)_+: w\in S^{d-1}\}$
%% under the metrics $d$ and $D$.

%% We start with bounding the covering numbers of $\F$ under the 
%% metric
%% \[
%% d(f,f')=\left(\EXP\left[\left((f(X)-\ol{\mu}_{f})-(f'(X)-\ol{\mu}_{f'})\right)^2\right]\right)^{1/2}~.
%% \]
%% First recall that by Lemma \ref{lem:firstterm}, for each
%% $f\in \F$, $|m_f-\ol{\mu}_f| \le \sqrt{\frac{v}{n}}$. 
%% Also, for $f(z,y)=(c-yw^Tz)_+$,
%% \[
%%   m_f= \EXP \left(c-Yw^TZ\right)_+ \le c + \sqrt{\EXP \left(w^TZ\right)^2}
%%    \le c+b \le \sqrt{v}~.
%% \]
%% Thus, for all $f\in \F$, $\ol{\mu}_f \in [0,2\sqrt{v}]$
%% and therefore the $\epsilon$-covering number of $\F$ under the metric
%% $d$ is at most
%% $4\sqrt{v}/\epsilon$ times the $(\epsilon/2)$-covering number of $\F$
%% under the $L_2$-metric
%% \[
%% d_2(f,f')\defeq \left(\EXP\left[\left(f(X)-f'(X)\right)^2\right]\right)^{1/2}~.
%% \]
%% However, by the Lipschitz property of $(\cdot)_+$ and Cauchy-Schwarz,
%% \[
%%  d_2(f,f')^2=
%% \EXP\left[\left(\left(c-Yw^TZ\right)_+-\left(c-Y{w'}^TZ\right)_+\right)^2\right]
%% \le \EXP \left((w-w')^TZ\right)^2 
%% \le \|w-w'\|^2 b^2~.
%% \]
%% Thus, the $(\epsilon/2)$-covering number of $\F$
%% under $d_2$ is at most the $(\epsilon/(2b))$-covering number of the unit sphere
%% $S^{d-1}$ under the Euclidean distance. By standard estimates, this 
%% is not more that $(8b/\epsilon)^d$. Thus, the 
%%  $\epsilon$-covering number of $\F$ under the metric
%% $d$ is bounded by
%% \[
%% \frac{ 4\sqrt{v}}{\epsilon} \left(\frac{ 8b}{\epsilon} \right)^d
%% \le \left(\frac{ 8\sqrt{v}}{\epsilon} \right)^{d+1}~.
%% \]
%% This implies that 
%% \[
%%   \gamma_2(\F,d) \le C \sqrt{dv}
%% \] 
%% for a universal constant $C$.
%% By a similar argument, one may estimate the 
%%  $\epsilon$-covering number of $\F$ under the metric
%% $D$ and find that it is bounded by
%% \[
%% \frac{ 4\sqrt{v}}{\epsilon} \left(\frac{ 8B}{\epsilon} \right)^d
%% \le \left(\frac{ 4\max(\sqrt{v},2B)}{\epsilon} \right)^{d+1}~.
%% \]
%% This leads to 
%% \[
%%   \gamma_1(\F,d) \le C' d\max(\sqrt{v},B)
%% \] 
%% for some other constant $C'$. 
%% Theorem \ref{thm:main} may now be applied to the support-vector classification
%% problem. One obtains that the excess risk (measured by the hinge loss) 
%% of $\wh{w}$ satisfies, with probability at least $1-\delta$,
%% \begin{eqnarray*}
%%  \EXP\left[ \left(c-Y\wh{w}^TZ\right)_+| (Z_1,Y_1),\ldots,(Z_n,Y_n)\right]
%% - \inf_{w\in S^{d-1}} \EXP \left(c-Yw^TZ\right)_+
%% \\
%% \le C \left(\log\frac{1}{\delta}\right) 
%%    \left[(c+b)\sqrt{\frac{d}{n}} + \max(c,B)\frac{d}{n} \right]~.
%% \end{eqnarray*}
%% **********CAN WE OBTAIN THIS FOR SIMPLE ERM? I THINK SO...**********

\subsubsection{$L_2$ regression}
\label{sec:l2}

Here we consider the same setup as in Section \ref{sec:L_1regr} but now the
risk is measured by the $L_2$ loss. 
The {\sl risk} of each $g\in \G$ is defined by the $L_2$ loss
\[
  R(g) = \EXP (g(Z)-Y)^2~.
\]
Note that Theorem 1 is useless here as the difference $|R(g)-R(g')|$ is not bounded by the $L_{\infty}$ distance
of $g$ and $g'$ anymore and the covering numbers of $\F$ under the metric $D$ are infinite.
However,  Theorem \ref{thm:alternative} gives meaningful bounds. 
Let $g^*= \argmin_{g\in \G} R(g)$ and again we choose $\wh{g}$ by minimizing Catoni's estimate.

Here we need to assume that 
$\EXP Y^4 \le \sigma^2$ for some $\sigma>0$. Then 
$\sup_{g\in \G} \var{(g(Z)-Y)^2}\le 8\sigma^2 + 8\sup_{g\in \G} \sup_{z\in \Z}|g(z)|^4
\defeq v$ is a known and finite constant.
% \emi{I have added the constant 8 missing in the previous definition of v}

By Theorem \ref{thm:alternative}, the performance of $\wh{g}$ may be 
bounded in terms of covering numbers of the class of functions 
$\F=\{f(z,y)=(g(z)-y)^2: g\in \G\}$ based on the distance
\[
  d_{\mathbb{X}}(f,f')=\left(\frac{1}{n}\sum_{i=1}^n\left((g(Z_i)-Y_i)^2
  -(g'(Z_i)-Y_i)^2 \right)^2\right)^{1/2}
\]
Note that
\begin{eqnarray*}
\left|(g(Z_i)-Y_i)^2-(g'(Z_i)-Y_i)^2 \right|&=&|g(Z_i)-g'(Z_i)||2Y_i-g(Z_i)-g'(Z_i)|\\
  &\le &  2|g(Z_i)-g'(Z_i)|(|Y_i|+\Delta)\\
&\le &  2d_{\infty}(g,g')(|Y_i|+\Delta)~,
\end{eqnarray*}
and therefore
\begin{eqnarray*}
d_{\mathbb{X}}(f,f') &\le & 2 d_{\infty}(g,g')\sqrt{\frac{1}{n}\sum_{i=1}^n(|Y_i|+\Delta)^2}\\
& \le &2 \sqrt{2} d_{\infty}(g,g')\sqrt{\Delta^2+\frac{1}{n}\sum_{i=1}^nY_i^2}~.
\end{eqnarray*}
By Chebyshev's inequality, 
$$ \prob{\frac{1}{n}\sum_{i=1}^nY_i^2 - \esp{Y^2}> t} \le \frac{\var{Y^2}}{nt^2} \le \frac{\sigma^2}{nt^2} $$
thus $ \frac{1}{n}\sum_{i=1}^nY_i^2 > \esp{Y^2} + \sqrt{8\sigma^2/(n\delta)} $ with probability at most $\delta/8$ and
$$ d_{\mathbb{X}}(f,f') > 2 \sqrt{2} d_{\infty}(g,g')\sqrt{\Delta^2+\esp{Y^2} + \sqrt{\frac{8\sigma^2}{n\delta}}}$$
occurs with a probability bounded by $\frac{\delta}{8}$. Recall again that for two distances $d_1$ and $d_2$ such that $d_1 \le cd_2$ one has $ \gamma_2(\G,d_1)\le c\gamma_2(\G,d_2) $. Then Theorem \ref{thm:alternative} applies with $$\Gamma_{\delta}=2\sqrt{2}\sqrt{\Delta^2+\esp{Y^2} + \sqrt{\frac{8\sigma^2}{n\delta}}}\gamma_2(\G,d_{\infty})$$
and $\Gamma_{\delta} \ge \Delta \ge \text{diam}_d(\F)$.
\begin{cor}
Consider the setup described above. Let $n\in \N$, $\delta\in (0,1/3)$ and $\alpha=\sqrt{2\log (\delta^{-1})/(nv)}$. There exists an integer $N_0$ and a universal
constant $C$ such that, for all $n \ge N_0$, with probability
at least $1-3\delta$, 
\begin{eqnarray*}
\lefteqn{   R(\wh{g}) - R(g^*)   }\\
& \le & 12\sqrt{\frac{2v\log (\delta^{-1})}{n}}+C\sqrt{\log \left(\frac{8}{\delta}\right)}\sqrt{\frac{\Delta^2+\esp{Y^2}+8\sigma^2/(n \delta)}{n}}\int_0^\Delta \sqrt{\log N_{\infty}(\G,\epsilon)}d\epsilon~.
\end{eqnarray*}
\end{cor}

\begin{proof}
Apply Theorem \ref{thm:alternative} and note that the condition holds for sufficiently large $n$.
\end{proof}

The bound of the corollary essentially matches the best rates of
convergence one can get even in the case of bounded regression
under such general conditions. For special cases, such as linear
regression, better bounds may be proven for other methods, see 
Audibert and Catoni \cite{AuCa11}, 
Hsu and Sabato
\cite{HsuSa13}, 
Minsker \cite{Min13}.

\subsection{k-means clustering under heavy tailed distribution}
\label{sec:kmeans}

In {\sl $k$-means clustering}---or {\sl vector quantization}---one
wishes to represent a distribution by a finite number of points.
Formally, let $X$ be a random vector taking values in $\R^m$
and let $P$ denote the distribution of $X$. 
Let $k\ge 2$ be a positive integer that we fix for the rest of
the section. A clustering scheme is given by 
 a set of $k$ cluster centers $C=\{y_1,\ldots,y_k\} \subset \R^m$
and a {\sl quantizer} $q:\R^m \to C$. Given a 
{\sl distortion measure} $\ell: \R^m\times \R^m \to [0,\infty)$,
one wishes to find $C$ and $q$ such that the expected
distortion 
\[
  D_k(P,q) = \EXP \ell(X,q(X)) 
\]  
is as small as possible. The minimization problem is
meaningful whenever $\EXP \ell(X,0) <\infty$ which we assume
throughout. Typical distortion measures are of the form
$\ell(x,y)=\|x-y\|^{\alpha}$ where $\|\cdot\|$ is a norm on $\R^m$
and $\alpha >0$ (typically $\alpha$ equals $1$ or $2$).
Here, for concreteness and simplicity, we assume
that $\ell$ is the Euclidean distance $\ell(x,y)=\|x-y\|$
though the results may be generalized in a straightforward manner
to other norms. 
In a way equivalent to the arguments of Section \ref{sec:l2}, 
the results may be
generalized to the 
case of the quadratic distortion $\ell(x,y)=\|x-y\|^2$. In order to avoid
repetition of arguments, the details are omitted.

It is not difficult to see that if $\EXP \|X\| < \infty$, then
there exists a (not necessarily unique) quantizer
$q^*$ that is optimal, that is, $q^*$ is such that for all clustering 
schemes $q$,
\[
    D_k(P,q) \ge D_k(P,q^*) \defeq D_k^*(P)~.
\]
It is also clear that $q^*$ is a {\sl nearest neighbor quantizer},
that is,
$$ \norm{x-q^*(x)}=\underset{y_i \in C}{\min}\norm{x-y_i}~. $$
Thus, nearest neighbor quantizers are determined by their cluster
centers $C=\{y_1,\ldots,y_k\}$. In fact, for all quantizers
with a particular set $C$ of cluster centers, the corresponding
nearest neighbor quantizer has minimal distortion and therefore 
it suffices to restrict our attention to nearest neighbor quantizers.

In the problem of empirical quantizer design, one is given 
an i.i.d.\ sample $X_1,\ldots,X_n$ drawn from the distribution $P$
and one's aim is to find a quantizer $q_n$ whose distortion
\[
  D_k(P,q_n) = \EXP \left[ \|X-q_n(X)\| \Big{|} X_1,\ldots,X_n \right]
\]
is as close to $D_k^*(P)$ as possible. A natural strategy is to 
choose a quantizer--or equivalently, a set $C$ of cluster centers--by
minimizing the {\sl empirical distortion}
\[
  D_k(P_n,q) = \frac{1}{n} \sum_{i=1}^n \|X_i-q(X_i)\|
           =  \frac{1}{n} \sum_{i=1}^n \min_{j=1,\ldots,k}\|X_i-y_j\|~,
\]
where $P_n$ denotes the standard empirical distribution 
based on $X_1,\ldots,X_n$. If $\EXP \|X\|<\infty$, then
the empirically optimal quantizer 
asymptotically minimizes the distortion. More precisely,
if $q_n$ denotes the empirically optimal
quantizer (i.e., $q_n=\argmin_q D_k(P_n,q)$), then 
\[
   \lim_{n\to \infty} D_k(P,q_n) = D_k^*(P) \quad \text{with probability $1$}, 
\]
see Pollard \cite{Pol81,Pol82a} 
and Abaya and Wise \cite{AbWi84} (see also
Linder \cite{Lin02}). The rate of convergence of 
$D_k(P,q_n)$ to $D_k^*(P)$ has drawn considerable attention,
see, e.g., Pollard \cite{Pol82b}, 
Bartlett, Linder, and Lugosi \cite{BaLiLu98},
Antos \cite{Ant05}, 
Antos, Gy\"orfi, and Gy\"orgy \cite{AnGyGy05},
Biau, Devroye, and Lugosi \cite{BiDeLu08},
Maurer and Pontil \cite{MaPo10}, and
Levrard \cite{Lev13}.
Such rates are typically studied under the assumption that 
$X$ is almost surely bounded. Under such assumptions one can show
that
\[
 \EXP D_k(P,q_n) - D_k^*(P) \le C(P,k,m) n^{-1/2}
\]
where the constant $C(P,k,m)$ depends on $\esssup \|X\|$, $k$, and the dimension
$m$. The value of the constant has mostly been investigated in the 
case of quadratic loss $\ell(x,y)=\|x-y\|^2$
but most proofs may be modified for the case studied here. 
For the quadratic loss, one may take $C(P,k,m)$ as a constant multiple
of $B^2\min(\sqrt{k^{1-2/m}m},k)$ where $B=\esssup \|X\|$. 

However, little is known about the finite-sample performance of empirically
designed quantizers under possibly heavy-tailed distributions. 
In fact, there is no hope to extend the results cited above for
distributions with finite second moment simply because empirical 
averages are poor estimators of means under such general conditions.

In the recent paper of Telgarsky and Dasgupta \cite{TeDa13}, bounds on the excess risk under  conditions on higher moments have been developed. 
They prove a bound of $ \mathcal{O}(n^{-1/2+2/p}) $ for the excess distortion  where $p$ is the number of moments of $\|X\|$ that are assumed to be finite. 
Here we show that there exists an empirical quantizer $\hat{q}_n$ 
whose excess distortion
$D_k(P,\wh{q}_n) - D_k^*(P)$ is of the order of $n^{-1/2}$ (with high probability)
under the only assumption that $\esp{\norm{X}^2}$ is finite.
This may be achieved by choosing a quantizer that minimizes 
Catoni's estimate of the distortion. 

The proposed empirical quantizer uses two parameters that depend on 
the (unknown) distribution of $X$. For simplicity, we assume that
upper bounds for these two parameters are available. (Otherwise either
one may try to estimate them or, as the sample size grows, use 
increasing values for these parameters. The details go beyond 
the scope of this paper.)

One of these parameters is the second moment $\var{X}=\esp{\norm{X-\esp{X}}^2}$ and let $V$ be
an upper bound. The other parameter $\rho>0$ is an upper bound 
for the norm of the possible cluster centers. 
The next lemma offers an estimate.


\begin{lem}
\label{lem-local} (Linder \cite{Lin02}.)
Let  $2\le j\le k$ be the unique integer 
such that $D^*_k=\cdots=D^*_j<D^*_{j-1}$
and define $\varepsilon = (D^*_{j-1}-D^*_j)/2$.
Let $(y_1,\dots,y_j)$ be a set of cluster centers such that
the distortion of the corresponding quantizer is less than 
$D^*_j+\varepsilon$. 
 Let $B_r =\{x:\norm{x} \le r\}$ denote the closed ball of radius $r>0$ centered at the origin. 
If $\rho>0$ is such that
\begin{itemize}
\item  $\frac{\rho}{10} P(B_{\frac{\rho}{10}}) > 2  \EXP\norm{X}$ 
\item $P(B_{2\rho/5})> 1- \frac{\varepsilon^2}{4\esp{\norm{X}^2}}$
\end{itemize}
then for all $1\le i \le k$, $\norm{y_i} \le \rho$.
\end{lem}

Now we are prepared to describe the proposed empirical quantizer.
Let $\C_{\rho}$ be the set of all collections 
$C=\{y_1,\ldots,y_k\} \in (\R^m)^k$ of cluster centers with
$\|y_j\|\le \rho$ for all $j=1,\ldots,k$.
For each $C\in \C_{\rho}$, denote by $q_C$ the corresponding 
quantizer. Now for all $C\in \C_{\rho}$, we may calculate 
Catoni's mean estimator of the distortion 
$D(P,q_C)= \EXP  \|X-q_C(X)\|= \EXP\min_{j=1,\ldots,k}\|X_i-y_j\|$ defined as
the unique value $\mu\in \R$ for which
\[
\frac{1}{n\alpha} \sum_{i=1}^n
\phi \left(\alpha\left(\min_{j=1,\ldots,k} \|X_i-y_j\|-\mu\right)\right) =0
\]
where we use the parameter value $\alpha=\sqrt{2/(nkV)}$.
Denote this estimator by $\wh{D}(P_n,q_C)$ and let $\wh{q}_n$ 
be any quantizer minimizing the estimated distortion.
An easy compactness argument shows that such a minimizer exists.

The main result of this section is the following bound
for the distortion of the chosen quantizer.

\begin{theorem}
Assume that $\var{X} \le V <\infty $ and $n\ge m$. Then, with probability at least $1-\delta$,
\[
D_k(P,\wh{q}_n)-D_k(P,q^*) \le C\left(\log \frac{1}{\delta}\right)
\left(\sqrt{\frac{Vk}{n}}+\sqrt{\frac{mk}{n}}\right)+O\left(\frac{1}{n}\right)~,
\]
where the constant $C$ only depends on $\rho$.
\end{theorem}

\begin{proof}
The result follows from Theorem \ref{thm:main}. All we need to check
is that $\var{\min_{j=1,\ldots,k} \|X-y_j\|}$ is bounded by $kV$
and estimate the covering numbers of the class of functions
\[
  \F_{\rho} = \left\{ f_C(x)=\min_{y \in C} \|x-y\|: C\in \C_{\rho} \right\}~.
\]
The variance bound follows simply by the fact that for all $C\in \C$,
\begin{eqnarray*}
\var{\min_{j=1,\ldots,k} \|X-y_j\|} &\le & \sum_{i=1}^k \var{\norm{X-y_i}}\\
&\le & \sum_{i=1}^k \esp{\norm{X-\EXP X}^2}+ \norm{\EXP X-y_i}^2-\esp{\norm{X-y_i}}^2 \le kV~.
\end{eqnarray*}
In order to use the bound of Theorem \ref{thm:main}, we need to
bound the covering numbers of the class $\F_{\rho}$ under both 
metrics $d$ and $D$. We begin with the metric
\[
D(f_C,f_{C'})=\sup_{x \in \R^m}| f_C(x)-f_{C'}(x) |~.
\]
The notation $B_z(\epsilon,d)$ refers to the ball under the metric $d$ of radius $\epsilon$ centered at $z$.
Let $Z$ be a subset of $B_{\rho}$ such that 
\[
\mathcal{B}_{B_{\rho}}:=\{B_{z}(\epsilon,\|\cdot\|): z \in Z\}
\]
is a covering of the set $B_{\rho}$ by balls of radius $\epsilon$ under the Euclidean norm. Let $C \in \mathcal{C}_{\rho}$ and associate to any $y_i \in C$ one of the centers in $Z$ such that $ \norm{y_i-z_i} \le \epsilon $. If there is more than one possible choice for $z_i $, we pick one of them arbitrarily. We denote by $ q_{C'} $ the nearest neighbor quantizer with codebook $C'=(z_i)_i $. Finally, let $S_i = q_{C'}^{-1}(z_i)$.
Now clearly, $\forall i,\ \forall x \in S_i $
\begin{eqnarray*}
f_C(x)-f_{C'}(x) &=& \min_{1\le j \le k} \|x-y_j\| -\min_{1\le j \le k} \|x-z_j\|\\
& = & \min_{1\le j \le k} \|x-y_j\| - \|x-z_i\|\\
&\le &  \|x-y_i\| - \|x-z_i\| \le \epsilon
\end{eqnarray*}
and similarly, $f_{C'}(x)-f_{C}(x)\le \epsilon$. Then $f_C \in B_{f_{C'}}(\epsilon,D)$ and
\[
\mathcal{B}_{\F_{\rho}}:= \{B_{f_{C}}(\epsilon,D): C \in Z^{k} \}
\]
is a covering of $ \F_{\rho} $. Since $Z$ can be taken such that $ |Z| = N_{\|\cdot\|}(B_{\rho},\epsilon)$ we obtain
\[
N_{d}(\F_{\rho},\epsilon) \le N_{D}(\F_{\rho},\epsilon) \le N_{\|\cdot\|}(B_{\rho},\epsilon)^k~.
\]
By standard estimates on the covering numbers of the ball $B_{\rho}$ by balls of size $\epsilon$ under the Euclidean metric,
\[
N_{\|\cdot\|}(B_\rho,\epsilon) \le \left(\frac{4\rho}{\epsilon}\right)^m
\]
(see, e.g., Matousek \cite{mat02}). 
In other words, there exists a universal constant $L$ and constants $C_\rho$ and $C'_\rho$ that depends only on $\rho$ such that
\begin{eqnarray*}
&\ & \gamma_2(\F_{\rho},d) \le L\int_{0}^{2\rho} \sqrt{\log N_{d}(\F_\rho,\epsilon)} d\epsilon \le C_\rho\sqrt{km}\\
&\text{and} & \gamma_1(\F_{\rho},D) \le L\int_{0}^{2\rho} \log N_{D}(\F_\rho,\epsilon) d\epsilon \le C'_\rho km~.
\end{eqnarray*}

Theorem \ref{thm:main} may now be applied to the class $\F_{\rho}$. 
\end{proof}


\section{Simulation Study}
\label{sec:sim}

In this closing section we present the results of two simulation exercises that assess the performance of the
estimators developed in this work.

\subsection{$L_2$ Regression}

The first application is an $L_2$ regression exercise. 
Data are simulated from a linear model with heavy-tailed errors and 
the $L_2$ regression procedure based on Catoni's risk minimizer 
introduced in Section \ref{sec:l2}
is used for estimation. The procedure is benchmarked against regular
(``vanilla'') $L_2$ regression based on the minimization of the empirical $L_2$ loss.

The simulation exercise is designed as follows.
We simulate $(Z_1,Y_1), (Z_2,Y_2), ..., (Z_n,Y_n)$ i.i.d.\ pairs of random variables in $\mathbb R^5 \times \mathbb R$.
%
The vector $Z_i$ of explanatory variables is drawn from a multivariate normal distribution with  zero mean, unit variance,
and correlation matrix equal to an equicorrelation matrix with correlation $\rho=0.9$.
% and kept fixed across simulation.
The response variable $Y_i$ is generated as
\[
	Y_i = Z_i^T\theta^* + \epsilon_i \;, 
\]
where the parameter vector $\theta^*$ is set to $(0.25, -0.25, 0.50, 0.70, -0.75)$
and $\epsilon_i$ is a zero mean error term.
The error term $\epsilon_i$ is drawn from a Pareto distribution with tail parameter $\beta$ and is appropriately recentered in order to have zero mean.
As it is well known, the tail parameter $\beta$ determines which moments of the Pareto random variable are finite.
More specifically, the moment of order $k$ exists only if $k < \beta$.
The focus is on finding the value of $\theta$ which minimizes the $L_2$ risk
\[
	\mathbb E \left| Y - Z_i^T\theta \right|^2 \;.
\]
The parameter $\theta$ is estimated using the Catoni and the vanilla $L_2$ regressions.
Let $\widehat{R}_C(\theta)$ denote the solution of the equation 
\[
	\hat r_\theta(\mu)=  {1 \over n\alpha} \sum_{i=1}^n \phi\left( \alpha\left( \left| Y_i - Z_i^T \theta \right|^2 - \mu \right) \right) = 0\;.
\]
Then the Catoni $L_2$ regression estimator is defined as
\[
	\wh{\theta}_{n\,C} = \arg \min_{\theta} \widehat{R}_C(\theta) \; . 
\]
The vanilla $L_2$ regression estimator is defined as the minimizer of the empirical $L_2$ loss, 
\[
	\wh{\theta}_{n\,V} = \arg \min_{\theta} \widehat{R}_V(\theta) = \arg \min_{\theta} {1 \over n}\sum_{i=1}^n \left| Y_i - Z_i^T\theta \right|^2 \;,
\]
which is the classical least squares estimator.
%The estimated risk of the Catoni and vanilla estimators are denoted as $\widehat R_C(\hat \theta_C)$ and $\widehat R_V(\hat \theta_V)$ respectively.
The precision of each estimator is measured by their excess risk 
\begin{equation*}
	\begin{array}{c c c}
	R(\wh{\theta}_{n\,C}) - R(\theta^*) & = & \mathbb E |Y - Z^{T}\wh{\theta}_{n\,C}|^2 - \mathbb E |Y - Z^{T}\theta^*|^2\\
	R(\wh{\theta}_{n\,V}) - R(\theta^*) & = & \mathbb E |Y - Z^{T}\wh{\theta}_{n\,V}|^2 - \mathbb E |Y - Z^{T}\theta^*|^2 \;.\\	
	\end{array} 
\end{equation*} 
We estimate excess risk by simulation. For each replication of the simulation exercise, we estimate the risk of the estimators and the optimal risk 
using sample averages based on an i.i.d. sample $(Z_1',Y_1'),\ldots, (Z_m',Y_m')$ that is independent of the one used for estimation, that is
\begin{equation}
	\begin{array}{c c c}
	\widetilde{R}(\wh{\theta}_{n\,C}) & = & {1 \over m} \sum_{i=1}^m |Y_i' - {Z_i'}^{T}\wh{\theta}_{n\,C}|^2  \\
	\widetilde{R}(\wh{\theta}_{n\,V})  & = & {1 \over m} \sum_{i=1}^m |Y_i' - {Z_i'}^{T}\wh{\theta}_{n\,V}|^2  \\	
	\widetilde{R}(\theta^*)  & = & {1 \over m} \sum_{i=1}^m |Y_i' - {Z_i'}^{T} \theta^*|^2 \; .
	\end{array}
	\label{eqn:lad:cen}
\end{equation}
The simulation experiment is replicated for different values of the Pareto tail parameter $\beta$ ranging from $2.01$ to $6.01$ and 
different values of the sample size $n$, ranging from $50$ to $1,000$.
For each combination of the tail parameter $\beta$ and sample size $n$, the experiment is replicated $1,000$ times.
%and report the average across all replications of the (simulated) average risk of Equations (\ref{eqn:lad:cen}).

%GL the green curve is invisible in the printout!!
\begin{figure}
	\begin{center}
	\caption{$L_2$ Regression Parameter Estimation.}
	$\begin{array}{c c}
		\includegraphics[width=0.45\textwidth]{regression_abs} &
		\includegraphics[width=0.45\textwidth]{regression_rel} \\
		\text{(a)} & \text{(b)} \\
	\end{array}$
	\label{fig:reg}
	\end{center}
	{\scriptsize The figure plots the excess risk of the Catoni and vanilla $L_2$ regression parameter estimators (a) and the percentage improvement of the Catoni procedure relative to the vanilla (b) as a function of the tail parameter $\beta$ for a sample size $n$ equal to 500.}
\end{figure}

%GL replace d by \beta in the table!!
\begin{table}
	\begin{center}
	\caption{Relative Performance of the Catoni $L_2$ Parameter Estimator.}
%	\include{reg_risk}	
	\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$\beta$&\textbf{n=50}&\textbf{n=100}&\textbf{n=250}&\textbf{n=500}&\textbf{n=750}&\textbf{n=1000}\\\hline
2.01&3872.10&440.50&171.30&222.70&218.20&142.80\\
2.50&169.20&158.70&151.50&106.70&91.70&57.40\\
3.01&137.60&178.00&89.00&52.50&62.70&63.50\\
3.50&54.40&20.90&41.30&39.20&38.10&33.50\\
4.01&30.20&44.40&25.50&15.70&16.30&15.90\\
4.50&16.50&12.10&11.30&10.60&6.90&13.70\\
5.01&10.20&7.80&10.20&6.40&5.70&3.10\\
5.50&6.00&14.80&3.90&2.90&2.10&2.20\\
6.01&3.90&1.90&2.70&2.10&1.90&1.40\\
\hline
\end{tabular}
	\label{tbl:reg}
	\end{center}
	{\scriptsize The table reports the percentage improvement of the excess risk of the Catoni $L_2$ regression estimator relative to the 
	vanilla procedure for different values of the tail parameter $\beta$ and sample size $n$.}
\end{table}

Figure \ref{fig:reg} displays the Monte Carlo estimate of the excess risk of the Catoni and benchmark regression estimators as functions of the tail parameter $\beta$ when the sample size $n$ is equal to $500$.
The left panel shows the level of the excess risks
$R(\wh{\theta}_{n\,C}) - R(\theta^*)$ and $R(\wh{\theta}_{n\,V}) - R(\theta^*)$
as a function of $\beta$
 and the right one shows the percentage improvement of the excess risk
 of the Catoni procedure over the benchmark calculated as
$\left(R(\wh{\theta}_{n\,V}) - R(\wh{\theta}_{n\,C})\right)/\left(R(\wh{\theta}_{n\,C}) - R(\theta^*)\right)$~.
%
When the tails are not excessively heavy (high values of $\beta$) the difference between the procedures is small.
As the tails become heavier (small values of $\beta$) the risks of both procedures increase.
%
Importantly, the Catoni estimator becomes progressively more efficient as the tails become heavier and becomes significantly more efficient when the tail parameter is close to $2$. 
%As expected, the improvement is greater for smaller sample sizes.
%Interestingly, the improvement of the procedure based on Catoni's estimate is minor in terms of the excess risk. 
%Our theoretical findings guarantee a controled excess risk for risk minimization based on Catoni's estimate while no such guarantees are available for vanilla empirical risk minimization. 
%However, at least in the experiments reported here, plain empirical risk minimization performs quite well.
%
Detailed results for different values of $n$ are reported in Table \ref{tbl:reg}.
%The pattern documented in the pictures holds for different values of $n$ but the advantages of the Catoni approach are stronger when the sample size $n$ is smaller.
Overall the Catoni $L_2$ regression estimator never performs worse than the benchmark and it is substantially better 
when the tails of the data are heavy.
 
\subsection{$k$-means}

%
In the second experiment we carry out a $k$--means clustering exercise.
Data are simulated from a heavy-tailed mixture distribution and then cluster centers are chosen
by minimizing Catoni's estimate of the $L_2$ distortion.
%The $k$--means algorithm based on Catoni is the standard $k$--means algorithm where the cluster center distortion is estimated using the Catoni estimator.
The performance of the algorithm is benchmarked against the (``vanilla'') $k$--means algorithm procedure
where the distortion is estimated by the standard empirical average.

%
The simulation exercise is designed as follows.
An i.i.d.\ sample of random vectors $X_1, ..., X_n$ in $\mathbb R^2$ is drawn from a four-component mixture distribution with equal weights.
The means of the mixture components are $(5,5), (-5,5), (-5,-5)$, and $(5,-5)$.
Each component of the mixture is made up of two appropriately centered independent draws from a Pareto distribution with tail parameter $\beta$.
%The random vector $X_i$ belonging to component $j$ is simualted as
%\[
%	X_{i}
%	=
%	\mu_j
%	+
%	\left[\begin{array}{c}
%	\epsilon_{i1} \\
%	\epsilon_{i2}
%	\end{array}\right]
%\]
%where $\epsilon_{i1}$ and $\epsilon_{i1}$ are independently drawn from a appropriately centered Pareto distribution with tail parameter $\beta$.
The cluster centers obtained by the $k$--means algorithm based on Catoni and the vanilla $k$--means algorithm are denoted respectively by $\wh{q}_{n\,C}$ and $\wh{q}_{n\,V}$.
%The estimated distortion of the estimated quantizers estimated by the two algorithms
%are denoted respectively as $D^C_k(P_n,\hat q^C_n)$ and $D_k(P_n,\hat q^V_n)$.
%Note that $D^C_k(P_n,\hat q^C_n)$ is estimated using the Catoni approach while $D_k(P_n,\hat q^C_n)$ is the simple empirical average $L_2$ loss.
%
%GL added this remark about k-means
(Since finding the empirically optimal cluster centers is
computationally prohibitive, we use the well-known iterative
optimization procedure ``$k$-means'' for the vanilla version and a
similar variant for the Catoni scheme.)
Analogously to the previous exercise, we summarize the performance of the clustering procedures using
the excess risk of the algorithms, that is
\begin{equation*}
	\begin{array}{c }
	D_k( P , \wh{q}_{n\,C} ) - D_k( P , q^* ) \\
	D_k( P , \wh{q}_{n\,V} ) - D_k( P , q^* )
	\end{array} \;,
\end{equation*}
where $q^*$ denotes the means of the mixture components.
We estimate excess risk by simulation. 
We compute the distortion of the quantizers using an
i.i.d.\ sample $X_1',\ldots, X_m'$ of vectors that is independent of the ones used for estimation, that is,
\begin{equation}
	\begin{array}{c c c}
	D_k(P_m,\wh{q}_{n\,C}) & = &  {1 \over m} \sum_{i=1}^m \min_{j=1,...,k} \left|\left| X_i' - \wh{q}_{n\,C}(X_i') \right| \right|^2 \\ 
	D_k(P_m,\wh{q}_{n\,V}) & = &  {1 \over m} \sum_{i=1}^m \min_{j=1,...,k} \left|\left| X_i' - \wh{q}_{n\,V}(X_i') \right| \right|^2 \\
	D_k(P_m,q^*) & = &  {1 \over m} \sum_{i=1}^m \min_{j=1,...,k} \left|\left| X_i' - q^*(X_i') \right| \right|^2  
	\end{array} \;.
	\label{eqn:kmeans:cen}
\end{equation}
The experiment is replicated for different values of the tail parameter $\beta$ ranging from $2.01$ to $6.01$  and different values of the sample size $n$ ranging from $50$ to $1,000$.
For each combination of tail parameter $\beta$ and sample size $n$ the experiment is replicated $1,000$ times.


\begin{figure}
	\begin{center}
	\caption{$k$--means Quantizer Estimation.}
	$\begin{array}{c c}
		\includegraphics[width=0.45\textwidth]{kmeans_abs} &
		\includegraphics[width=0.45\textwidth]{kmeans_rel} \\
		\text{(a)} & \text{(b)} \\
	\end{array}$
	\label{fig:kmeans}
	\end{center}
	{\scriptsize The figure plots the excess risk of the Catoni and vanilla $k$--means quantizer estimator (a) and the percentage improvement of the Catoni procedure relative to the vanilla (b) as a function of the tail parameter $\beta$ for a sample size $n$ equal to 500.}
\end{figure}

\begin{table}
	\begin{center}
	\caption{Relative Performance of the Catoni $k$--means Quantizer Estimator.}
%	\include{kmeans_risk}	
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\textbf{$\beta$}&\textbf{n=50}&\textbf{n=100}&\textbf{n=250}&\textbf{n=500}&\textbf{n=750}&\textbf{n=1000}\\\hline
2.01&823.80&2180.40&3511.60&6278.90&7858.70&10684.60\\
2.50&404.50&1007.40&2959.80&4255.40&6828.60&9093.60\\
3.01&301.10&312.20&286.80&298.60&813.60&1560.20\\
3.50&129.60&188.60&213.30&271.40&448.60&410.00\\
4.01&73.80&30.90&26.80&20.30&18.20&13.10\\
4.50&27.60&22.90&16.50&11.70&9.50&10.10\\
5.01&16.40&10.80&11.60&8.70&6.00&7.20\\
5.50&9.00&6.80&9.20&5.00&4.10&4.00\\
6.01&3.50&4.70&5.00&2.70&3.20&3.10\\
\hline
\end{tabular}

	\label{tbl:kmeans}
	\end{center}
	{\scriptsize The table reports the improvement of the Catoni $k$--means quantizer estimator relative to the 
	vanilla procedure for different values of the tail parameter $\beta$ and sample size $n$.}
\end{table}

%For each set of simulations we compute the Monte Carlo average the performance indices in Equations (\ref{eqn:q}) and (\ref{eqn:d}).
Figure \ref{fig:kmeans} displays the Monte Carlo estimate of excess risk of the Catoni and benchmark estimators as a function of tail parameter $\beta$ for $n=500$.
The left panel shows the estimated excess risk while the right panel shows the percentage improvement of the excess risk of the Catoni procedure, calculated as
$\left(D_k( P , \wh{q}_{n\,V} )-D_k( P , \wh{q}_{n\,C} )\right)/
\left(D_k( P , \wh{q}_{n\,C} ) - D_k( P , q^* )\right)$.

%
The overall results are analogous to the ones of the $L_2$ regression application.
When the tails of the mixture are not excessively heavy (high values of $\beta$) the difference in the procedures is small.
As the tails become heavier (small values of $\beta$) the risk of both 
procedures increases,
but the Catoni algorithm becomes progressively more efficient.
The percentage gains for the Catoni procedure are substantial when the tail parameter is smaller than $4$.
%
Table \ref{tbl:kmeans} reports detailed results for different values of $n$.
%The pattern documented in the pictures holds for different values of $n$ but the advantages of the Catoni are more marked when the sample size $n$ is smaller.
As in the $L_2$ regression simulation study, the Catoni $k$--means algorithm never performs worse than the benchmark and it is substantially better when the tails of the mixture are heavy.

\section{Appendix}
\subsection{A chaining theorem}
The following result is a version of standard bounds based on
``generic chaining'', see Talagrand \cite{talagrand}. We include 
the proof for completeness.

Recall that if $\psi$ is a non-negative increasing convex function
defined on $\R_+$ with $\psi(0)=0$, then
the Orlicz norm of a random variable $X$ is defined by 
\[
 \|X\|_{\psi} = \inf \left\{c>0\ :\ \esp{\psi\left(\frac{|X|}{c}\right)}\le  1 \right\}~.
\]
We consider Orlicz norms defined by
\[
\psi_1(x) =\exp(x)-1 \quad \text{and} \quad
\psi_2(x)=\exp(x^2)-1~.
\]
For further information on Orlicz norms see \cite[Chapter 2.2]{vaWe96}. First, $\orlic{X}{1}\le \orlic{X}{2}\sqrt{\log (2)}$ holds. 
Also note that, by Markov's inequality, $\orlic{X}{1}\le c$ implies 
that $\PROB\{|X|>t\}\le 2e^{-t/c}$ and similarly, if
$\orlic{X}{2}\le c$, then $\PROB\{|X|>t\}\le 2e^{-t^2/c^2}$.
Then
\begin{eqnarray}
\label{eq-orlic}
&X \le \orlic{X}{1}\log (2\delta^{-1})\quad &\text{with probability at least } 1-\delta~,\\
&X \le \orlic{X}{2}\sqrt{\log(2\delta^{-1})}\quad &\text{with probability at least } 1-\delta~.
\nonumber
\end{eqnarray}
Recall the following definition (see, e.g., \cite[Definition 1.2.3]{talagrand}).
Let $T$ be a (pseudo) metric space. An increasing sequence 
$(\mathcal{A}_n)$ of partitions of $T$ is called {\sl admissible} if
for all $n=0,1,2,\ldots,$  $\#\mathcal{A}_n \le 2^{2^n}$. 
For any $t\in T$, denote by $A_n(t)$ the unique element 
of $\mathcal{A}_n$ that contains $t$.
Let $\Delta(A)$ denote the diameter of the set $A\subset T$.
Define, for $\beta =1,2$,
\[
\gamma_{\beta}(T,d)
  =\inf_{\mathcal{A}_n}\sup_{t \in T} \sum_{n \ge 0} 2^{n/\beta}\Delta(A_n(t))~,
\]
where the infimum is taken over all admissible sequences. First of all, we know from \cite[Eq. (1.18)]{talagrand} that there exists a universal constant $L$ such that
\begin{equation}
\label{eq:dudley}
\gamma_{\beta}(T,d) \le L \int_0^{\text{diam}_d(T)}\left(\log N_d(T,\varepsilon)\right)^{\frac{1}{\beta}}d\varepsilon
\end{equation}
%\emi{Added here the Dudley bound}




\begin{theorem}
\label{thm:chaining}
Let $(X_t)_{t\in T}$ be a stochastic process indexed by a set $T$ on which 
two (pseudo) metrics, $d_1$ and $d_2$, are defined such that $T$ is bounded
with respect to both metrics.  
Assume that for any $s,t \in T$ and for all $x>0$,
\[
\PROB\{|X_s-X_t|>x \}
   \le 2\exp \left(-\frac{1}{2}\frac{x^2}{d_2(s,t)^2+d_1(s,t)x}\right)~.
\]

Then for all $t\in T$,
\[
\orlic{\sup_{s \in T} |X_s-X_t|}{1} 
\le L \left( \gamma_1(T,d_1) + \gamma_2(T,d_2) \right)
\]
with $L\le 384 \log(2)$.
\end{theorem}
The proof of Theorem \ref{thm:chaining} uses the following lemma:

\begin{lem}
\label{lem:vvw}
{\sc (\cite[lemma 2.2.10]{vaWe96}.)}
Let $a,b>0$ and assume that the random variables $X_1,\dots,X_m$ satisfy,
for all $x>0$, 
\[
\PROB\{|X_i|>x\} \le 2\exp \left(-\frac{1}{2}\frac{x^2}{b+ax}\right)~.
\]
Then
\[
\orlic{\max_{1\le i \le m} X_i}{1}
\le 48 \left(a\log(1+m) +\sqrt{b} \sqrt{\log(1+m)} \right)~.
\]
\end{lem}

\begin{proof}[Proof of Theorem \ref{thm:chaining}]
Consider an admissible sequence $(\mathcal{B}_n)_{n \ge 0}$ such that
for all $t \in T$,
\[
 \sum_{n \ge 0} 2^n \Delta_1(B_n(t)) \le 2 \gamma_1(T,d_1)
\]
and an admissible sequence $(\mathcal{C}_n)_{n \ge 0}$ such that
for all $t \in T$,
\[
\sum_{n \ge 0} 2^{n/2} \Delta_2(C_n(t)) \le 2 \gamma_2(T,d_2)~.
\]
Now we may define an admissible sequence by intersection of the elements of $(\mathcal{B}_{n-1})_{n \ge 1}$ and $(\mathcal{C}_{n-1})_{n \ge 1}$:
set $\mathcal{A}_0=\{T\}$ and let
\[
\mathcal{A}_n =\{ B\cap C\ :\ B \in \mathcal{B}_{n-1}\ \&\ C\in \mathcal{C}_{n-1}\}~.
\]
$(\mathcal{A}_n)_{n \ge 0}$ is an admissible sequence because 
each $\mathcal{A}_n$ is increasing and contains at most $(2^{2^{n-1}})^2=2^{2^n}$ sets.
Define a sequence of finite sets $T_0=\{t\}\subset T_1\subset \dots \subset T$
such that $T_n$ contains a single point in each set of $\mathcal{A}_n$. 
For any $s \in T$, denote by $\pi_n(s)$ the unique element of 
$T_n$ in $A_n(s)$.
Now for any $s \in T_{k+1}$, we write
\[
X_s-X_t= \sum_{k=0}^\infty
\left(X_{\pi_{k+1}(s)}-X_{\pi_{k}(s)}\right)~.
\] 
Then, using the fact that $\orlic{\cdot}{1}$ is a norm and 
Lemma \ref{lem:vvw}, 
\begin{eqnarray*}
\lefteqn{
\orlic{\sup_{s \in T} |X_s-X_t|}{1} }  \\
& \le & \sum_{k=0}^\infty \orlic{\max_{s \in T_{k+1}} |X_{\pi_{k+1}(s)}-X_{\pi_{k}(s)}|}{1}\\
& \le & 
48\sum_{k=0}^\infty \left(d_1(\pi_{k+1}(s),\pi_{k}(s))\log(1+2^{2^{k+1}})+d_2(\pi_{k+1}(s),\pi_{k}(s))\sqrt{\log(1+2^{2^{k+1}})} \right)~.
\end{eqnarray*}
Since $(\mathcal{A}_n)_{n \ge 0}$ is an increasing sequence,
$\pi_{k+1}(s)$ and $\pi_{k}(s)$ are both in $A_k(s)$. By construction,
$A_k(s) \subset B_k(s)$, and therefore $d_1(\pi_{k+1}(s),\pi_{k}(s))
\le \Delta_1(B_k(s))$. Similarly,  we have $d_2(\pi_{k+1}(s),\pi_{k}(s)) \le \Delta_2(C_k(s))$. 
Using  $\log(1+2^{2^{k+1}}) \le 4\log (2) 2^k$, we get
\begin{eqnarray*}
\orlic{\max_{s \in T} |X_s-X_t|}{1} &\le& 192 \log(2) \left[ \sum_{k=0}^\infty 2^k \Delta_1(B_k(s))+\sum_{k=0}^\infty 2^{k/2} \Delta_2(C_k(s))\right]\\
&\le& 384 \log(2) \left[ \gamma_{1}(T,d_1)+\gamma_{2}(T,d_2)\right]~.
\end{eqnarray*}
\end{proof}
\begin{proposition}
\label{cor:orlic}
Assume that for any $s,t \in T$ and for all $x>0$,
\[
\PROB\{|X_s-X_t|>x \}
   \le 2\exp \left(-\frac{x^2}{2d_2(s,t)^2}\right)~.
\]
Then for all $t\in T$,
\[
\orlic{\sup_{s \in T} |X_s-X_t|}{2} 
\le L \gamma_2(T,d_2) 
\]
where $L$ is a universal constant.
\end{proposition}

%G I wrote this instead of the proof:
The proof of Proposition \ref{cor:orlic} is 
similar to the proof of Theorem \ref{thm:chaining}.
One merely needs to replace Lemma \ref{lem:vvw} by Lemma 2.2.2 in \cite{vaWe96}
and proceed identically. The details are omitted.

We may use Proposition \ref{cor:orlic} to bound the moment generating
function of $\sup_{s \in T} |X_s-X_t|$ as follows.
Set $S = \sup_{s \in T} |X_s-X_t|$. Then using $ab \le (a^2+b^2)/2$,
we have, for every $\lambda >0$,
\[
\exp (\lambda S) \le \exp\left(S^2/\norm{S}^2_{\psi_2}+\lambda^2\norm{S}^2_{\psi_2}/4\right)~,
\]
and therefore
\begin{equation}
\label{eq:charac}
\esp{\exp (\lambda \sup_{s \in T} |X_s-X_t|)} \le 2\exp (\lambda^2 L^2 \gamma_2(T,d_2)^2/4)~.
\end{equation}



%% \begin{proof}[Proof of Proposition \ref{cor:orlic}]
%% The proof is similar to the proof of Theorem \ref{thm:chaining}. Consider an admissible sequence $(\mathcal{A}_n)_{n \ge 0}$ such that
%% for all $t \in T$,
%% \[
%% \sum_{n \ge 0} 2^{n/2} \Delta_2(A_n(t)) \le 2 \gamma_2(T,d_2)
%% \]
%% and a sequence of finite sets $T_0=\{t\}\subset T_1\subset \dots \subset T$
%% such that $T_n$ contains a single point in each set of $\mathcal{A}_n$. We start from a similar result as Lemma \ref{lem:vvw} that is Lemma 2.2.2 in \cite{vaWe96}. Under the hypothesis of Lemma \ref{lem:vvw}, there exists a universal constant $K$ such that one has
%% \[
%% \orlic{\max_{1\le i \le m} X_i}{2} \le K\sqrt{b}\sqrt{\log (1+m)}~.
%% \]
%% Following the arguments of Theorem \ref{thm:chaining} we get
%% \begin{eqnarray*}
%% \orlic{\sup_{s \in T} |X_s-X_t|}{2} & \le & \sum_{k=0}^\infty \orlic{\max_{s \in T_{k+1}} |X_{\pi_{k+1}(s)}-X_{\pi_{k}(s)}|}{2}\\
%% & \le & 
%% K\sum_{k=0}^\infty d_2(\pi_{k+1}(s),\pi_{k}(s))\sqrt{\log(1+2^{2^{k+1}})}\\
%% & \le & 8K\log (2) \gamma_2(T,d_2) ~.
%% \end{eqnarray*}
%% \end{proof}
%% %\emi{I have added the proof of the second report on the calculation of\esp{\exp (\lambda \sup_{s \in T} |X_s-X_t|)}}


\medskip\noindent{\bf Acknowledgments.} \ We thank the referees for their thorough reading and insightful comments that helped greatly improve the manuscript.


\bibliographystyle{plain}
%GL update Lerasle  Oliveira; Mendelson, Minsker, Hsu & Sabato papers
%\bibliography{biblio}
\begin{thebibliography}{10}

\bibitem{AbWi84}
E.~A. Abaya and G.~L. Wise.
\newblock Convergence of vector quantizers with applications to optimal
  quantization.
\newblock {\em SIAM Journal on Applied Mathematics}, 44:183--189, 1984.

\bibitem{AMS02}
N.~Alon, Y.~Matias, and M.~Szegedy.
\newblock The space complexity of approximating the frequency moments.
\newblock {\em Journal of Computer and System Sciences}, 58:137--147, 2002.

\bibitem{Ant05}
A.~Antos.
\newblock Improved minimax bounds on the test and training distortion of
  empirically designed vector quantizers.
\newblock {\em IEEE Transactions on Information Theory}, 51:4022--4032, 2005.

\bibitem{AnGyGy05}
A.~Antos, L.~Gy\"orfi, and A.~Gy\"orgy.
\newblock Improved convergence rates in empirical vector quantizer design.
\newblock {\em IEEE Transactions on Information Theory}, 51:4013--4022, 2005.

\bibitem{AuCa11}
J.-Y. Audibert and O.~Catoni.
\newblock Robust linear least squares regression.
\newblock {\em The Annals of Statistics}, 39:2766--2794, 2011.

\bibitem{BaLiLu98}
P.~Bartlett, T.~Linder, and G.~Lugosi.
\newblock The minimax distortion redundancy in empirical quantizer design.
\newblock {\em IEEE Trans. Inform. Theory}, 44:1802--1813, Sep. 1998.

\bibitem{BaMe06}
P.L. Bartlett and S.~Mendelson.
\newblock Empirical minimization.
\newblock {\em Probability Theory Related Fields}, 135:311--334, 2006.

\bibitem{BiDeLu08}
G.~Biau, L.~Devroye, and G.~Lugosi.
\newblock On the performance of clustering in {H}ilbert spaces.
\newblock {\em IEEE Transactions on Information Theory}, 54:781--790, 200.

\bibitem{BoBoLu05}
S.~Boucheron, O.~Bousquet, and G.~Lugosi.
\newblock Theory of classification: a survey of some recent advances.
\newblock {\em ESAIM. Probability and Statistics}, 9:323--375, 2005.

\bibitem{gabor}
S.~Boucheron, G.~Lugosi, and P.~Massart.
\newblock {\em Concentration Inequalities: A Nonasymptotic Theory of
  Independence}.
\newblock Oxford University Press, 2013.

\bibitem{BuCeLu13}
S.~Bubeck, N.~Cesa-Bianchi, and G.~Lugosi.
\newblock Badits with heavy tail.
\newblock {\em IEEE Transactions on Information Theory}, 59:7711--7717, 2013.

\bibitem{Cat10}
O.~Catoni.
\newblock Challenging the empirical mean and empirical variance: a deviation
  study.
\newblock {\em Annales de l'Institut Henri Poincar{\'e}, Probabilit{\'e}s et
  Statistiques}, 48(4):1148--1185, 2012.

\bibitem{Dud78}
R.M. Dudley.
\newblock Central limit theorems for empirical measures.
\newblock {\em Annals of Probability}, 6:899--929, 1978.

\bibitem{Emb97}
P.~Embrechts, C.~Kl\"uppelberg, and T.~Mikosch.
\newblock {\em Modelling Extremal Events for Insurance anf Finance}.
\newblock Springer-Verlang, Frankfurt, 1997.

\bibitem{Fam63}
E.~F. Fama.
\newblock Mandelbrot and the stable {P}aretian hypothesis.
\newblock {\em The Journal of Business}, 36:420--429, 1963.

\bibitem{Fin03}
B.~Finkenstadt and H.~Rootz\'en.
\newblock {\em Extreme Values in Finance, Telecommunications and the
  Enviroment}.
\newblock Chapman and Hall, New York, 2003.

\bibitem{HsuSa13}
D.~Hsu and S.~Sabato.
\newblock Approximate loss minimization with heavy tails.
\newblock {\em Computing Research Repository}, abs/1307.1827, 2013.

\bibitem{Kol06}
V.~Koltchinskii.
\newblock Local {R}ademacher complexities and oracle inequalities in risk
  minimization.
\newblock {\em Annals of Statistics}, 36:00--00, 2006.

\bibitem{LeOl12}
M.~Lerasle and R.I. Oliveira.
\newblock Robust empirical mean estimators.
\newblock {\em manuscript}, 2012.

\bibitem{Lev13}
C.~Levrard.
\newblock Fast rates for empirical vector quantization.
\newblock {\em Electronic Journal of Statistics}, pages 1716--1746, 2013.

\bibitem{Lin02}
T.~Linder.
\newblock Learning-theoretic methods in vector quantization.
\newblock In L.~Gy\"orfi, editor, {\em Principles of nonparametric learning},
  number 434 in {CISM} Courses and Lecture Notes. Springer-Verlag, New York,
  2002.

\bibitem{Man63}
B.~Mandelbrot.
\newblock The variation of certain speculative prices.
\newblock {\em The Journal of Business}, 36:394--419, 1963.

\bibitem{Mas06}
P.~Massart.
\newblock {\em Concentration inequalities and model selection}.
\newblock Ecole d'\'et\'e de Probabilit\'es de Saint-Flour 2003. Lecture Notes
  in Mathematics. Springer, 2006.

\bibitem{mat02}
J.~Matou{\v{s}}ek.
\newblock {\em Lectures on discrete geometry}.
\newblock Springer, 2002.

\bibitem{MaPo10}
A.~Maurer and M.~Pontil.
\newblock $k$-dimensional coding schemes in {H}ilbert spaces.
\newblock {\em IEEE Transactions on Information Theory}, 56:5839--5846, 2010.

\bibitem{Men14}
S.~Mendelson.
\newblock Learning without concentration.
\newblock {\em arXiv preprint arXiv:1401.0304}, 2014.

\bibitem{Min13}
S.~Minsker.
\newblock Geometric median and robust estimation in {B}anach spaces.
\newblock {\em arXiv preprint}, 2013.

\bibitem{NeYu83}
A.S. Nemirovsky and D.B. Yudin.
\newblock Problem complexity and method efficiency in optimization.
\newblock 1983.

\bibitem{Pol81}
D.~Pollard.
\newblock Strong consistency of $k$-means clustering.
\newblock {\em Annals of Statistics}, 9, no. 1:135--140, 1981.

\bibitem{Pol82b}
D.~Pollard.
\newblock A central limit theorem for $k$-means clustering.
\newblock {\em Annals of Probability}, 10(4):919--926, 1982.

\bibitem{Pol82a}
D.~Pollard.
\newblock Quantization and the method of $k$-means.
\newblock {\em IEEE Trans. Inform. Theory}, IT-28:199--205, 1982.

\bibitem{talagrand}
M.~Talagrand.
\newblock {\em The generic chaining}.
\newblock Springer, 2005.

\bibitem{TeDa13}
M.~Telgarsky and S.~Dasgupta.
\newblock Moment-based uniform deviation bounds for $ k $-means and friends.
\newblock {\em arXiv preprint arXiv:1311.1903}, 2013.

\bibitem{Geer00}
S.~van~de Geer.
\newblock {\em Empirical Processes in {M}-Estimation}.
\newblock Cambridge University Press, Cambridge, UK, 2000.

\bibitem{vaWe96}
A.W. {van der Vaart} and J.A. Wellner.
\newblock {\em Weak convergence and empirical processes}.
\newblock Springer-Verlag, New York, 1996.

\end{thebibliography}

\end{document} 


\end{document} 

kmeans_risk.tex
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\textbf{$\beta$}&\textbf{n=50}&\textbf{n=100}&\textbf{n=250}&\textbf{n=500}&\textbf{n=750}&\textbf{n=1000}\\\hline
2.01&823.80&2180.40&3511.60&6278.90&7858.70&10684.60\\
2.50&404.50&1007.40&2959.80&4255.40&6828.60&9093.60\\
3.01&301.10&312.20&286.80&298.60&813.60&1560.20\\
3.50&129.60&188.60&213.30&271.40&448.60&410.00\\
4.01&73.80&30.90&26.80&20.30&18.20&13.10\\
4.50&27.60&22.90&16.50&11.70&9.50&10.10\\
5.01&16.40&10.80&11.60&8.70&6.00&7.20\\
5.50&9.00&6.80&9.20&5.00&4.10&4.00\\
6.01&3.50&4.70&5.00&2.70&3.20&3.10\\
\hline
\end{tabular}

reg_risk.tex
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
$\beta$&\textbf{n=50}&\textbf{n=100}&\textbf{n=250}&\textbf{n=500}&\textbf{n=750}&\textbf{n=1000}\\\hline
2.01&3872.10&440.50&171.30&222.70&218.20&142.80\\
2.50&169.20&158.70&151.50&106.70&91.70&57.40\\
3.01&137.60&178.00&89.00&52.50&62.70&63.50\\
3.50&54.40&20.90&41.30&39.20&38.10&33.50\\
4.01&30.20&44.40&25.50&15.70&16.30&15.90\\
4.50&16.50&12.10&11.30&10.60&6.90&13.70\\
5.01&10.20&7.80&10.20&6.40&5.70&3.10\\
5.50&6.00&14.80&3.90&2.90&2.10&2.20\\
6.01&3.90&1.90&2.70&2.10&1.90&1.40\\
\hline
\end{tabular}

1406.2462.extracted_bib
{AbWi84 E.~A. Abaya and G.~L. Wise. \newblock Convergence of vector quantizers with applications to optimal quantization. \newblock {\em SIAM Journal on Applied Mathematics, 44:183--189, 1984.
1406.2462.extracted_bib
{AMS02 N.~Alon, Y.~Matias, and M.~Szegedy. \newblock The space complexity of approximating the frequency moments. \newblock {\em Journal of Computer and System Sciences, 58:137--147, 2002.
1406.2462.extracted_bib
{Ant05 A.~Antos. \newblock Improved minimax bounds on the test and training distortion of empirically designed vector quantizers. \newblock {\em IEEE Transactions on Information Theory, 51:4022--4032, 2005.
1406.2462.extracted_bib
{AnGyGy05 A.~Antos, L.~Gy\"orfi, and A.~Gy\"orgy. \newblock Improved convergence rates in empirical vector quantizer design. \newblock {\em IEEE Transactions on Information Theory, 51:4013--4022, 2005.
1406.2462.extracted_bib
{AuCa11 J.-Y. Audibert and O.~Catoni. \newblock Robust linear least squares regression. \newblock {\em The Annals of Statistics, 39:2766--2794, 2011.
1406.2462.extracted_bib
{BaLiLu98 P.~Bartlett, T.~Linder, and G.~Lugosi. \newblock The minimax distortion redundancy in empirical quantizer design. \newblock {\em IEEE Trans. Inform. Theory, 44:1802--1813, Sep. 1998.
1406.2462.extracted_bib
{BaMe06 P.L. Bartlett and S.~Mendelson. \newblock Empirical minimization. \newblock {\em Probability Theory Related Fields, 135:311--334, 2006.
1406.2462.extracted_bib
{BiDeLu08 G.~Biau, L.~Devroye, and G.~Lugosi. \newblock On the performance of clustering in {Hilbert spaces. \newblock {\em IEEE Transactions on Information Theory, 54:781--790, 200.
1406.2462.extracted_bib
{BoBoLu05 S.~Boucheron, O.~Bousquet, and G.~Lugosi. \newblock Theory of classification: a survey of some recent advances. \newblock {\em ESAIM. Probability and Statistics, 9:323--375, 2005.
1406.2462.extracted_bib
{gabor S.~Boucheron, G.~Lugosi, and P.~Massart. \newblock {\em Concentration Inequalities: A Nonasymptotic Theory of Independence. \newblock Oxford University Press, 2013.
1406.2462.extracted_bib
{BuCeLu13 S.~Bubeck, N.~Cesa-Bianchi, and G.~Lugosi. \newblock Badits with heavy tail. \newblock {\em IEEE Transactions on Information Theory, 59:7711--7717, 2013.
1406.2462.extracted_bib
{Cat10 O.~Catoni. \newblock Challenging the empirical mean and empirical variance: a deviation study. \newblock {\em Annales de l'Institut Henri Poincar{\'e, Probabilit{\'es et Statistiques, 48(4):1148--1185, 2012.
1406.2462.extracted_bib
{Dud78 R.M. Dudley. \newblock Central limit theorems for empirical measures. \newblock {\em Annals of Probability, 6:899--929, 1978.
1406.2462.extracted_bib
{Emb97 P.~Embrechts, C.~Kl\"uppelberg, and T.~Mikosch. \newblock {\em Modelling Extremal Events for Insurance anf Finance. \newblock Springer-Verlang, Frankfurt, 1997.
1406.2462.extracted_bib
{Fam63 E.~F. Fama. \newblock Mandelbrot and the stable {Paretian hypothesis. \newblock {\em The Journal of Business, 36:420--429, 1963.
1406.2462.extracted_bib
{Fin03 B.~Finkenstadt and H.~Rootz\'en. \newblock {\em Extreme Values in Finance, Telecommunications and the Enviroment. \newblock Chapman and Hall, New York, 2003.
1406.2462.extracted_bib
{HsuSa13 D.~Hsu and S.~Sabato. \newblock Approximate loss minimization with heavy tails. \newblock {\em Computing Research Repository, abs/1307.1827, 2013.
1406.2462.extracted_bib
{Kol06 V.~Koltchinskii. \newblock Local {Rademacher complexities and oracle inequalities in risk minimization. \newblock {\em Annals of Statistics, 36:00--00, 2006.
1406.2462.extracted_bib
{LeOl12 M.~Lerasle and R.I. Oliveira. \newblock Robust empirical mean estimators. \newblock {\em manuscript, 2012.
1406.2462.extracted_bib
{Lev13 C.~Levrard. \newblock Fast rates for empirical vector quantization. \newblock {\em Electronic Journal of Statistics, pages 1716--1746, 2013.
1406.2462.extracted_bib
{Lin02 T.~Linder. \newblock Learning-theoretic methods in vector quantization. \newblock In L.~Gy\"orfi, editor, {\em Principles of nonparametric learning, number 434 in {CISM Courses and Lecture Notes. Springer-Verlag, New York, 2002.
1406.2462.extracted_bib
{Man63 B.~Mandelbrot. \newblock The variation of certain speculative prices. \newblock {\em The Journal of Business, 36:394--419, 1963.
1406.2462.extracted_bib
{Mas06 P.~Massart. \newblock {\em Concentration inequalities and model selection. \newblock Ecole d'\'et\'e de Probabilit\'es de Saint-Flour 2003. Lecture Notes in Mathematics. Springer, 2006.
1406.2462.extracted_bib
{mat02 J.~Matou{\v{sek. \newblock {\em Lectures on discrete geometry. \newblock Springer, 2002.
1406.2462.extracted_bib
{MaPo10 A.~Maurer and M.~Pontil. \newblock $k$-dimensional coding schemes in {Hilbert spaces. \newblock {\em IEEE Transactions on Information Theory, 56:5839--5846, 2010.
1406.2462.extracted_bib
{Men14 S.~Mendelson. \newblock Learning without concentration. \newblock {\em arXiv preprint arXiv:1401.0304, 2014.
1406.2462.extracted_bib
{Min13 S.~Minsker. \newblock Geometric median and robust estimation in {Banach spaces. \newblock {\em arXiv preprint, 2013.
1406.2462.extracted_bib
{NeYu83 A.S. Nemirovsky and D.B. Yudin. \newblock Problem complexity and method efficiency in optimization. \newblock 1983.
1406.2462.extracted_bib
{Pol81 D.~Pollard. \newblock Strong consistency of $k$-means clustering. \newblock {\em Annals of Statistics, 9, no. 1:135--140, 1981.
1406.2462.extracted_bib
{Pol82b D.~Pollard. \newblock A central limit theorem for $k$-means clustering. \newblock {\em Annals of Probability, 10(4):919--926, 1982.
1406.2462.extracted_bib
{Pol82a D.~Pollard. \newblock Quantization and the method of $k$-means. \newblock {\em IEEE Trans. Inform. Theory, IT-28:199--205, 1982.
1406.2462.extracted_bib
{talagrand M.~Talagrand. \newblock {\em The generic chaining. \newblock Springer, 2005.
1406.2462.extracted_bib
{TeDa13 M.~Telgarsky and S.~Dasgupta. \newblock Moment-based uniform deviation bounds for $ k $-means and friends. \newblock {\em arXiv preprint arXiv:1311.1903, 2013.
1406.2462.extracted_bib
{Geer00 S.~van~de Geer. \newblock {\em Empirical Processes in {M-Estimation. \newblock Cambridge University Press, Cambridge, UK, 2000.
1406.2462.extracted_bib
{vaWe96 A.W. {van der Vaart and J.A. Wellner. \newblock {\em Weak convergence and empirical processes. \newblock Springer-Verlag, New York, 1996.