\section{Introduction}
The well-known {\em Cage Problem} is the problem of finding $k$-regular graphs of girth $g$
(which we shall call $(k,g)${\em -graphs})
and smallest possible orders for all pairs of parameters $ k \geq 2, g \geq 3 $ (with the smallest
graphs called $(k,g)${\em -cages}). An exact solution
for the Cage Problem is only known for very limited sets of parameter pairs $(k,g)$, in particular,
for the cases when the orders of the $(k,g)$-cages match a simple lower bound
due to Moore \cite{ExooJaj08}. These special graphs are called {\em Moore graphs}, and in the case
of even $g=6,8$ or $12$, Moore graphs are known to be the point-block incidence graphs of projective planes, generalized hexagons, and generalized quadrangles, respectively.

Due to the universally acknowledged complexity of the Cage Problem - and also to
gain additional insights - several relaxations of the original problem have been introduced
\cite{BobJajPis,ExooJaj08}. One
such relaxation focuses on biregular graphs of girth $g$ and calls for finding smallest graphs
of girth $g$ admitting a two-element degree set $\{ n,m \} $
\cite{AraExoJaj,ExooJaj16,FuLaSeUsWol95}. Naturally,
considering graphs from these more relaxed classes requires correspondingly adjusting the
Moore bounds. Unlike the case of the classical Cage Problem, biregular graphs of degrees
$n,m$ and girth $g$ whose orders match the adjusted Moore bound were shown to exist for
all pairs $n,m$ where $m$ is considerably larger than $n$ and $g$ is odd \cite{ExooJaj16}.
However, the case of even girth remains wide open \cite{AraExoJaj,YuLi03}. A well-known
conjecture concerning $(k,g)$-cages of even girth asserts that all even girth cages ought to be
bipartite (see, for example, \cite{Fil17,JaFiJa16}). In connection to this conjecture,
a further specialization of the biregular cage problem has been introduced in \cite{FilRamRivJaj19},
in which the authors proposed to study the {\em {bipartite biregular}} $(n,m;g)$-graphs which are
bipartite graphs of even girth $g$ having the degree set $\{n,m\}$ and satisfying the additional property that the vertices in the same partite set have the same degree. This is also the class we
consider in our paper. The corresponding {\em adjusted Moore lower bounds} $B(n,m;2r)$ for the orders of the bipartite biregular $(n,m;2r)$-cages derived in \cite{FilRamRivJaj19} take the form:
\begin{eqnarray*}\label{Moore:bound-even}
1  + & (m-1)+(m-1)(n-1)+\ldots+(m-1)^{\frac{r}{2}}(n-1)^{\frac{r}{2}-1} +\\
1 + & (n-1)+(n-1)(m-1)+\ldots+(n-1)^{\frac{r}{2}}(m-1)^{\frac{r}{2}-1},
\end{eqnarray*}
when $r$ is even, and
\begin{eqnarray*}\label{Moore:bound-odd}
1+ & (m-1)+(m-1)(n-1)+\ldots+(m-1)^{\frac{r-1}{2}}(n-1)^{\frac{r-1}{2}} + \\
1+ & (n-1)+(n-1)(m-1)+\ldots+(n-1)^{\frac{r-1}{2}}(m-1)^{\frac{r-1}{2}},
\end{eqnarray*}
when $r$ is odd.

The difference between the order of a bipartite biregular $(n,m;2r)$-graph $G$ and
the corresponding adjusted Moore bound $B(m,n;2r)$ is called the {\em excess} of $G$,
and in \cite{FilRamRivJaj19}, the authors succeeded at proving the non-existence of bipartite
$(m,n;g)$-graphs of excess at most $4$ for all parameters $m, n, g$ where $g\geq10$ and is
not divisible by $4$, and $m > n\geq3$. They also proved for all pairs $m,n$, $m>n\geq 3$, that the asymptotic density of the set of even girths $g\geq8$ for which there exists a bipartite $(m,n;g)$-graph with excess not exceeding $4$ is equal to $0$. Following
the usual way of naming graphs whose orders match the Moore bound, we shall call bipartite biregular $(n,m;2r)$-graphs whose orders match the corresponding adjusted Moore bound (\ref{Moore:bound-even}) or
(\ref{Moore:bound-odd}) {\em  bipartite biregular Moore $(n,m;2r)$-cages}.

In this paper, we use a a connection to balanced incomplete block designs to present infinite families of bipartite biregular Moore $(n,m;6)$-cages; and, for larger girths,
we explore a connection between bipartite biregular Moore $(n,m;g)$-graphs,
$ g = 8,12 $ or $16$, and generalized polygons. Our approach is analogous to a well
established connection between the existence of $(k,g)$-Moore graphs and finite geometries.

\section{Preliminaries}
In this section we introduce definitions and theorems concerning block designs and generalized polygons which are well-known to experts in these fields. Nevertheless,
for the sake of completeness, we include these as they will be used throughout our paper.

\subsection{Block designs and Steiner systems}\label{BDSS}
\label{sec:pre}
All definitions and results given in this subsection can be found for example in \cite{ColDin}.

\begin{definition}
A {\em balanced incomplete block design} (BIBD) is a collection of $k$-subsets (called {\em blocks}) of a $v$-set $S$, $k<v$, such that each pair of elements of $S$ occur together in exactly $\lambda$  blocks.
\end{definition}
The number of blocks is denoted by $b$ and the design is denoted as a $(v,k,\lambda)$-{\em design}.

\begin{theorem}
\label{eq}
In a $(v,k,\lambda)$-design with $b$ blocks each element occurs in $r$ blocks where:
\begin{enumerate}
\item $r(k-1)=\lambda(v-1)$, and
\item $vr=bk$.
\end{enumerate}
\end{theorem}
Sometimes a $(v,k,\lambda)$-design is described as a $(v,b,r,k,\lambda)$-design, but it is important to realize that, once $v$, $k$ and $\lambda$ are known, the other two parameters are uniquely determined.
The next concept is a generalization of a BIBD.

\begin{definition}
Let $t,\ v,\ k,\ \lambda$ be integers with $v\geq k\geq t \geq 2$ and $\lambda > 0$. A $t-(v,k,\lambda)$-{\em design} is a collection of $k$-subsets ({\em blocks}) of a $v$-set $S$ such that every $t$-subset of $S$ is contained in exactly $\lambda$ blocks. We observe that a $2$-design is just a BIBD.
\end{definition}

A Steiner system is a $t$-design with $\lambda=1$, that is:

\begin{definition}
A {\em{Steiner system}} $S(t,k,v)$ is a collection of $k$-subsets (blocks) of a $v$-subset $S$ such that every $t$-subset of $S$ is contained in exactly one of the blocks. Note that we use $S(t,k,v)$ as an equivalent to $t-(k,v,1)$. Note also that Steiner systems $S(2,k,v)$ are just $(v,k,1)$ BIBDs.
\end{definition}

In this paper, we will be specifically interested in Steiner systems, for which we will show that their
point-block incidence graphs are related to  bipartite biregular cages; the main topic of our paper.
In particular, we obtain our best results when $k=3$, in which case the Steiner systems $S(2,3,v)$  are called {\em Steiner triple systems} and are denoted by $STS(v)$.\\

The equalities given in Theorem \ref{eq} yield that if a Steiner system exists, it necessarily holds that $v\equiv 1  \pmod{k(k-1)}$ or $v\equiv k  \pmod{k(k-1)}$.

Steiner systems are known to exist for certain specific values of $k$ and $v$, but the general question for
which values of $k$ there exists a Steiner system is a well-known open problem; the congruences given above constitute necessary but not sufficient conditions. However, for $k=3$, it has already been proved by
Kirkman that these conditions are both necessary and sufficient, and an $STS(v)$ exists if and only
$ v \geq 7 $ is congruent to $1$ or $3$ modulo $6$ \cite{ColDin}.

\subsection{Generalized Polygons}\label{QHG}
To learn more about the definitions and results given in this subsection consult for
example \cite{VM98}. A {\em geometry} $ (\cal{P},\cal{L},{\bf I}) $ is a triple consisting
of disjoint sets $ \cal{P} $  and $ \cal{L} $, called {\em points} and {\em lines} related through the {\em incidence relation} $ {\bf I} \subseteq \cal{P} \times \cal{L} $
that determines which points from $ \cal{P} $ belong to which lines in $ \cal{L} $.
An {\em ordinary} $n${\em -gon} arises naturally from the regular $n$-gon in the
plane.

\begin{definition}
Let $n\geq 1$ be a natural number. A {\em weak generalized $n$-gon} is a geometry
$\Gamma = (\cal{P},\cal{L},{\bf I})$ such that the following two axioms are satisfied:
\begin{enumerate}
\item $\Gamma$ contains no ordinary $k$-gon (as a subgeometry) for $2\leq k < n.$
\item Any two elements $x,y \in \cal{P}\cup\cal{L}$ are contained in some ordinary $n$-gon (again as a subgeometry) in $\Gamma$.
\vskip 2mm

\hskip -4.5mm
A {\em generalized $n$-gon} is a weak generalized $n$-gon $\Gamma$ which satisfies the additional axiom:
\item There exists an ordinary $(n+1)$-gon (as a subgeometry) in $\Gamma$.
\end{enumerate}
\end{definition}

As with the Steiner systems, we will be interested in the point-line incidence graphs
of (weak) generalized $n$-gons. The following lemma establishes the fundamental
connection.

\begin{lemma}[\cite{VM98}, Lemma 1.3.6]\label{VMLemma}
A geometry $\Gamma = (\cal{P},\cal{L},{\bf I})$ is a (weak) generalized $n$-gon if and
only if the incidence graph of $\Gamma$ is a connected graph of diameter $n$ and
girth $2n$, such that each vertex lies on at least three (at least two) edges.
\end{lemma}

Every generalized polygon $\Gamma$ can be associated with a pair $(s,t)$,
called the {\em order} of $\Gamma$, such that every line is incident with $s+1$
points, and every point is incident with $t+1$ lines \cite{VM98}. This means,
in particular, that the incidence graph of $\Gamma$ is a bipartite biregular graph
with the two degrees $s+1$ and $t+1$. In addition, the following result
determines the orders of the two partite sets.

\begin{theorem}[\cite{VM98}, Corollary 1.5.5]\label{PL}
If there exists a $\Gamma = (\cal{P},\cal{L},{\bf I})$ (weak) generalized $n$-gon of order $(s,t)$ for $n \in \{3,4,6,8\}$ then:
\[ | {\cal P} | = \left\{ \begin{array}{cr} s^2+s+1 & \mbox{ if } n=3; \\
(1+s)(1+st), & \mbox{ if } n=4; \\
(1+s)(1+st+s^2t^2), & \mbox{ if } n=6; \\ (1+s)(1+st)(1+s^2t^2), & \mbox{ if } n=8.
\end{array} \right. \]
\[ |{\cal L} | = \left\{ \begin{array}{cr} t^2+t+1 & \mbox{ if } n=3; \\
(1+t)(1+st), & \mbox{ if } n=4; \\
(1+t)(1+st+s^2t^2), & \mbox{ if } n=6; \\ (1+t)(1+st)(1+s^2t^2), & \mbox{ if } n=8.
\end{array} \right. \]
\end{theorem}
In 1964, Feit and Higman proved that finite generalized $n$-gons exist only for $n=\{3,4,6,8\}$. When $n=3$, we have the projective planes; when $r=4$, we have the generalized quadrangles, which are known to exist when $s=t$ or $t=s^2$; when $r=6$, we have the generalized hexagons, which also exist in the regular case $s=t$
and when $t=s^3$; and finally, for $r=8$, we have the generalized octagons, which only exist when $s=t^2$.

The rest of the paper is dedicated to our contributions.
\section {Bipartite biregular cages of girth 6}
\label{sec:girth6}

As argued in \cite{FilRamRivJaj19,YuLi03}, any $(n,m;6)$-graph has at least the following number of vertices
\begin{equation}
\label{eq:1}
n_0(n,m;6)=\left\lceil n+m+2(m-1)(n-1)+ \frac{(m-1)(n-1)(m-n)}{n}\right\rceil =\left\lceil \frac{(m+n)(mn-m+1)}{n}\right\rceil,
\end{equation}
and we shall call the graphs whose orders attain this lower bound the {\em $(n,m;6)$-Moore cages}. In general, given an $(n,m;6)$-graph $G$, {\em the excess} of $G$ is
the difference $e=|V(G)|-n_0(n,m;6)$.

\subsection{Bipartite biregular Moore cages associated to Steiner systems}
In this section we will prove that the existence of a Steiner system immediately yields
the existence of a bipartite biregular Moore cage.

\begin{theorem}
\label{the: S(2,k,v)}
The point-block incidence graph $G$ of a Steiner system $S(2,k,v)$, $ k \geq 3 $, is a
(bipartite biregular) $(k,r;6)$-Moore cage, where $r=\frac{v-1}{k-1}$.
\end{theorem}
\begin{proof}
The fact that the point-block incidence graph $G$ of a Steiner system $S(2,k,v)$,
$ k \geq 3 $, is a $(k,r;6)$-graph is fairly obvious: Each point belongs to $r$ blocks,
each block contains $k$ vertices, $G$ is bipartite and therefore contains even length
cycles only, and the existence of a $4$-cycle in $G$ would force the two vertices of
the $4$-cycle to belong to both of its blocks, which would violate the condition $ \lambda
=1 $. Since every pair of vertices belongs to a block, any $3$-set of vertices
not belonging to the same block of the Steiner system together with the three blocks containing the three $2$-subsets of this $3$-set forms a $6$-cycle.

Thus, to complete the proof of our theorem, we only need to show that the order of the
point-block incidence graph $G$ of a Steiner system $S(2,k,v)$ attains the lower
bound (\ref{eq:1}). Using Theorem~\ref{eq} implies $v=r(k-1)+1$ and $r=bk/v$, and
therefore
$$ | V(G) | = v+b=(r(k-1)+1) + \left(\frac{r^2(k-1)+r}{k}\right)$$
$$=\frac{(r+k)(rk-r+1)}{k} =\left\lceil \frac{(r+k)(rk-r+1)}{k} \right\rceil.$$
Hence, $ | V(G) | = n_0(r,k;6) $, as defined in (\ref{eq:1}), and the incidence graph of
the Steiner system $S(2,k,v)$ is a $(k,r;6)$-Moore cage.
\end{proof}

Obviously, the above graphs are truly biregular only if $ r \neq k $. Recall that if
the Steiner system $S(2,k,v)$ is in fact a projective plane of order $r-1$, then $r=k$.
Thus, Theorem~\ref{the: S(2,k,v)} is a generalization of the well-known result
stating that
the point-line incidence graph of a projective plane of order $q$ is a $(q+1,6)$-Moore
cage (see, e.g., \cite{ExooJaj08}).
Moreover, as the affine plane of order $q$ is also a Steiner system $S(2,q,q^2)$,
we have the following result:

\begin{corollary}
\label{cor:affine planes}
The point-line incidence graph $G$ of an affine plane of order $q$ is a
(bipartite biregular) $(q,q+1;6)$-Moore cage.
\end{corollary}
In particular, Figure 5 in \cite{FilRamRivJaj19} is the incidence graph of a affine plane of order $3$.

\subsection{Bipartite biregular  cages associated with Steiner triple system.}
The results of the previous subsection show that the existence of a Steiner system
$S(2,k,v)$ gives rise to a bipartite biregular $(k,r;6)$-Moore cage, where the parameter
$r$ is determined by the parameters $k$ and $v$. Since no classification of the
parameter pairs $(k,v)$ admitting the existence of an $S(2,k,v)$ exists, this type of
result does not allow for classifying the parameter pairs $(k,r)$ admitting the existence
of a bipartite biregular $(k,r;6)$-Moore cage.

As pointed out in Section~\ref{BDSS}, the $k=3$ situation is different in that we have
a classification of the pairs $(3,v)$ that admit the existence of an $S(2,3,v)$.
Thus, in this section we will focus on Steiner triple systems and determine the orders
of the $(3,m;6)$-bipartite biregular cages for all values of $m$.

Recall that a Steiner triple system $STS(v)$ exists if and only if $ v \geq 7 $ and
$v\equiv 1,3 \ (\mod{6})$; in which case $ r = \frac{v-1}{k-1} = \frac{1}{2}(v-1) $.
Thus, Theorem~\ref{the: S(2,k,v)} implies the existence of a bipartite biregular
$(k,r;6)$-Moore cage for all $r$ of the form $ \frac{1}{2}(6m+1-1)=3m$ or $
 \frac{1}{2}(6m+3-1)=3m+1$, $ m \geq 1 $. Hence, we know the orders of
 $(3,m;6)$-bipartite biregular cages for two thirds of parameters $m$, $ m \equiv 0 $
 and $ m \equiv 1 \pmod{3} $. In the rest
 of this section, we will focus on the remaining unresolved case $ m \equiv 2 \pmod{3} $.

\begin{lemma}
\label{le:5}
Let $m>4$ be an integer. If $m\equiv 2 \pmod{3}$, then the order $|V(G)|$ of any
$(3,m;6)$-graph $G$ satisfies the inequality:
$$\frac{2m^2+7m+3}{3}+\frac{m+3}{3} \leq  |V(G)|.$$
\end{lemma}
\begin{proof}
Let $m>4$, $m\equiv 2 \pmod{3}$, and let $G$ be a $(3,m;6)$-bipartite biregular graph with
the sets $A$ and $B$ forming the partition of $V(G)$; with $A$ of cardinality $a$
containing the vertices of degree $m$, and $B$ of cardinality $b$ containing the vertices of degree $3$. The order of $G$ is then equal to $a+b$, and since the number of edges
leaving $A$ must be equal to the number of edges entering $B$, $am=3b$.
The lower bound from formula (\ref{eq:1}) takes the form
\[ n_0(3,m;6)=\left\lceil \frac{(m+3)(3m-m+1)}{3}\right\rceil = \left\lceil  \frac{2m^2+7m+3}{3}   \right\rceil , \]
and since $ m \equiv 2 \pmod{3} $,
\[ n_0(3,m;6)= \left\lceil  \frac{2m^2+7m+3}{3}   \right\rceil = \frac{2m^2+7m+3}{3} + \frac{2}{3} . \]

\noindent
Let $e$ denote the excess of $G$ (as compared to $n_0(3,m;6)$), and recall that $b=\frac{am}{3}$. Then,
$$ |V(G) | =\frac{2m^2+7m+3}{3} + \frac{2}{3} + e = \frac{2m^2+7m+3+2+3e}{3} , $$
while also $ |V(G) | = a+\frac{am}{3} $,
and therefore
$$a(3+m)=2m^2+7m+3+2+3e . $$
In particular, $a=\frac{2m^2+7m+3+2+3e}{m+3}$ must be an integer.
Since $2m^2+7m+3 = (m+3)(2m+1)$, the expression $m+3$ divides $2m^2+7m+3$ evenly, and therefore
the remaining fraction $\frac{2+3e}{m+3}$ must be an integer
as well. However, if $e$ were smaller than $\frac{m+1}{3}$, we would have $\frac{2+3e}{m+3} < 1$, and
therefore, $ \frac{m+1}{3}  \leq e$.

Thus,
\[ |V(G)| = \frac{2m^2+7m+3+2}{3}+e \geq \frac{2m^2+7m+3}{3}+\frac{m+3}{3} . \]

\end{proof}

\begin{theorem}
\label{le:STS}
Let $m>3$ be an integer.
\begin{enumerate}
\item If $m \equiv 0,1 \pmod{3}$, then a $(3,m;6)$-biregular bipartite cage is the point-block incidence graph of
the Steiner triple system $STS(2m+1)$ of order $n_0(3,m;6)$.
\item If $m \equiv 2 \pmod{3}$, then the order of a $(3,m;6)$-biregular bipartite cage is
$n_0(3,m;6)+\frac{m+3}{3}$.
\end{enumerate}
\end{theorem}

\begin{proof}
If $m \equiv 0,1 \pmod{3}$, then $2m+1 \equiv 1 $ or $3 \pmod{6}$, the Steiner triple system
$STS(2m+1)$ exists, and its point-block incidence graph of order $n_0(3,m;6)$
is a $(3,m;6)$-biregular bipartite cage as argued in Theorem~\ref{the: S(2,k,v)}.

Next assume that $m \equiv 2 \pmod{3}$. Lemma~\ref{le:5} asserts that the order of any
$(3,m;6)$-biregular bipartite graph $G$ is greater than or equal to $n_0(3,m;6)+\frac{m+3}{3}$.
Thus, to prove the second claim of our theorem, we just need to prove the existence of a
$(3,m;6)$-biregular bipartite graph $G$ of order equal to $n_0(3,m;6)+\frac{m+3}{3}$.

Since $m \equiv 2 \pmod{3}$, it follows that $2m+3 \equiv 1 \ (\mod{6})$, and thus an $STS(2m+3)$
exists. Let $G'$ be the $(3,m+1;6)$-biregular bipartite incidence graph of this Steiner triple system.
We shall construct the desired $(3,m;6)$-biregular bipartite graph $G$ of order $n_0(3,m;6)+\frac{m+3}{3}$
by removing vertices and edges from the graph $G'$.

Let $x$ be a point and $b$ be a block of the $STS(2m+3)$ containing $x$. Let $f=(x,b)$ be an edge of
$G'$, and let $G=G'[X]$ be the subgraph of $G'$ induced by the vertex set $X=V(G')\backslash (x\cup N(x))$,
where $N(x)$ is the neighborhood of $x$ in $G'$, i.e., the set of all blocks of the $STS(2m+3)$ containing
$x$. We claim that $G$ is a $(3,m;6)$-biregular bipartite graph (see Figure \ref{fig:G}).
First, none of the remaining blocks contains the
point $x$, and hence each of them is connected to $3$ of the remaining points. Hence all the remaining
blocks represent vertices of degree $3$ and no two of them are adjacent. As for the remaining points, they
all have been originally adjacent to $m+1$ blocks, and are now adjacent to one less block - the block they
shared with $x$ - and hence represent mutually non-adjacent vertices of degree $m$. Since $G$ contains
no vertices of degree $1$ or $0$, it is not a forest and contains at least one cycle. We claim that the number
of vertices of $G$ is too small for $G$ to be of girth $8$. To prove this, as well as to prove that $G$ is a
$(3,m;6)$-cage, we determine the order of $G$:
$$
\begin{array}{ccccccccc}
|V(G)|&=&|V(G')|-1-(m+1)\\
&=&\frac{2(m+1)^2+7(m+1)+3}{3}-2-m\\
&=&\frac{2m^2+4m+2+7m+7+3-6-3m}{3}\\
&=&\frac{2m^2+8m+6}{3} \\
&=&\frac{2m^2+7m+3}{3}+\frac{m+3}{3}\\
&=&n_0(3,m;6)+\frac{m+3}{3}.\\

\end{array}
$$
Thus, $G$ has the desired order. As proved in \cite{FilRamRivJaj19}, the order of any $(3,m;8)$-biregular
bipartite graph is bounded from below by
\[ 1 + 2 + 2(m-1) + 4(m-1) + 1 + (m-1) + 2(m-1) + 2(m-1)^2 = -3 + 5m + 2m^2, \]
a value that is clearly bigger than $ |V(G)| = \frac{2m^2+8m+6}{3} $, and thus the girth of $G$ cannot
be $8$.

\begin{figure}[h!]
\begin{center}
\psset{xunit=.7cm,yunit=.7cm,algebraic=true,dimen=middle,dotstyle=o,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(5.2,1.45)(13.68,9.8)
\rput{0}(7,4){\psellipse(0,0)(1.2,0.67)}
\rput{0}(11.86,4.04){\psellipse(0,0)(1.2,0.67)}
\rput{0}(7,7){\psellipse(0,0)(1.2,0.67)}
\rput{0}(12,7){\psellipse(0,0)(1.2,0.67)}
\rput{0}(7,9){\psellipse(0,0)(1.2,0.67)}
\psline(8,2)(11,2)

\psline(8,2)(7.02,3.34)
\psline(8,2)(7.52,3.4)
\psline(8,2)(6.47,3.4)

\psline(11,2)(12.04,3.38)
\psline(11,2)(11.58,3.39)

\psline(12,4.7)(12,6.33)
\psline(12.5,4.6)(12.5,6.39)
\psline(11.5,4.67)(11.5,6.41)

\psline(6.52,4.61)(6.44,6.41)
\psline(7.46,4.62)(7.49,6.39)

\psline(6.7,7.64)(6.7,8.36)
\psline(7,7.67)(7,8.33)
\psline(7.3,7.63)(7.3,8.37)

\rput[lt](10.93,4.44){\parbox{1.6 cm}{\tiny{$2$ vertices  \\ corresponding \\  to points}}}
\rput[lt](6.05,4.44){\parbox{1.6 cm}{\tiny{$m$ vertices  \\ corresponding \\  to blocks}}}
\rput[lt](6.08,7.4){\parbox{1.65 cm}{\tiny{$2m$ vertices  \\ corresponding \\  to points}}}
\rput[lt](11.08,7.4){\parbox{1.65 cm}{\tiny{$2m$ vertices  \\ corresponding \\  to blocks}}}
\rput[lt](6.08,9.41){\parbox{1.65 cm}{\tiny{$4m$ vertices  \\ corresponding \\  to blocks}}}
\rput[tl](7.85,1.8){$x$}
\rput[tl](10.85,1.9){$b$}
\psline[linewidth=1.6pt,linestyle=dashed,dash=4pt 4pt](5.85,6.28)(12.7,1.99)
\begin{scriptsize}
\psdots[dotstyle=*](8,2)
\psdots[dotstyle=*](11,2)
\end{scriptsize}
\end{pspicture*}
\caption{A sketch of how to obtain $G$.}
\label{fig:G}
\end{center}
\end{figure}
\end{proof}

For an example, consider Figure \ref{fig:m5} which depicts a part of the bipartite biregular graph $G'$ that is a $(3,6;6)$-Moore cage. It is the incidence graph of a Steiner triple system $STS(13)$ with the blue points corresponding to the $13$ elements (denoted as $\{0,1,\ldots,9,A,B,C\}$) and the red points corresponding to the $26$ blocks (note that the edges that are not drawn in Figure \ref{fig:m5} can be easily determined by the incidence rule: the point
$x$ belongs to the blocks $xyz$ independently of the values of $y$ an $z$).

\begin{figure}[htbp]
\begin{center}
\psset{xunit=1.0cm,yunit=1.0cm,algebraic=true,dimen=middle,dotstyle=o,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-1.2,0.61)(11.95,7.84)
\rput[tl](-0.25,4.95){\footnotesize{$1$}}
\rput[tl](.12,4.95){\footnotesize{$4$}}
\rput[tl](0.72,4.95){\footnotesize{$2$}}
\rput[tl](1.1,4.95){\footnotesize{$8$}}
\rput[tl](1.72,4.95){\footnotesize{$9$}}
\rput[tl](2.05,4.95){\footnotesize{$A$}}
\rput[tl](2.7,4.95){\footnotesize{$B$}}
\rput[tl](3.1,4.95){\footnotesize{$6$}}
\rput[tl](3.75,4.95){\footnotesize{$C$}}
\rput[tl](4.1,4.95){\footnotesize{$3$}}

\rput[tl](-0.2,7.45){\footnotesize{$186$}}
\rput[tl](0.6,7.45){\footnotesize{$42A$}}
\rput[tl](1.5,7.45){\footnotesize{$1AB$}}
\rput[tl](2.6,7.45){\footnotesize{$89C$}}
\rput[tl](3.6,7.45){\footnotesize{$49A$}}
\rput[tl](4.55,7.45){\footnotesize{$46C$}}
\rput[tl](5.6,7.45){\footnotesize{$263$}}
\rput[tl](6.6,7.45){\footnotesize{$2B6$}}
\rput[tl](7.6,7.45){\footnotesize{$8A3$}}
\rput[tl](8.6,7.45){\footnotesize{$193$}}

\rput[tl](-0.5,3.4){\footnotesize{$014$}}
\rput[tl](0.5,3.4){\footnotesize{$028$}}
\rput[tl](1.4,3.4){\footnotesize{$9A0$}}
\rput[tl](2.25,3.4){\footnotesize{$B06$}}
\rput[tl](3.1,3.4){\footnotesize{$C03$}}

\rput[tl](1.9,1.3){\footnotesize{$0$}}
\rput[tl](7.7,1.3){\footnotesize{$570$}}
\rput[tl](6.15,3.4){\footnotesize{$5$}}
\rput[tl](8.98,3.4){\footnotesize{$7$}}

\rput[tl](7.9,4.95){\footnotesize{$1C7$}}
\rput[tl](8.65,5.4){\footnotesize{$347$}}
\rput[tl](9.2,5.4){\footnotesize{$67A$}}
\rput[tl](9.75,5.4){\footnotesize{$78B$}}
\rput[tl](10.4,5.4){\footnotesize{$792$}}

\rput[tl](4.86,4.95){\footnotesize{$125$}}
\rput[tl](5.6,5.4){\footnotesize{$AC5$}}
\rput[tl](7.3,5.4){\footnotesize{$35A$}}
\rput[tl](6.25,5.4){\footnotesize{$458$}}
\rput[tl](6.8,5.4){\footnotesize{$569$}}

\psline(2,1.5)(8,1.5)
\psline(6.5,3.5)(8,1.5)
\psline(8,1.5)(9.5,3.5)
\psline(2,1.5)(0,3.5)
\psline(2,1.5)(3,3.5)
\psline(6.5,3.5)(6,5)
\psline(6.5,3.5)(7,5)
\psline(6.5,3.5)(5.5,5)
\psline(2,1.5)(4,3.5)
\psline(2,1.5)(2,3.5)
\psline(2,1.5)(1,3.5)
\psline(6.5,3.5)(6.5,5)
\psline(6.5,3.5)(7.5,5)
\psline(9.5,3.5)(9.5,5)
\psline(9.5,3.5)(9,5)
\psline(9.5,3.5)(8.5,5)
\psline(9.5,3.5)(10,5)
\psline(9.5,3.5)(10.5,5)
\psline(4,3.5)(4.4,5)
\psline(4,3.5)(3.6,5)
\psline(3,3.5)(3.4,5)
\psline(3,3.5)(2.6,5)
\psline(2,3.5)(2.4,5)
\psline(2,3.5)(1.6,5)
\psline(1,3.5)(1.4,5)
\psline(0.6,5)(1,3.5)
\psline(0,3.5)(0.4,5)
\psline(0,3.5)(-0.4,5)

\psline(-0.4,5)(1.8,7)
\psline(-0.4,5)(0,7)
\psline(0.4,5)(3.8,7)
\psline(0.4,5)(0.8,7)
\psline(0.4,5)(4.8,7)
\psline(0.6,5)(6.8,7)
\psline(0.6,5)(5.8,7)
\psline(0.6,5)(0.8,7)
\psline(1.4,5)(0,7)
\psline(1.4,5)(2.8,7)
\psline(1.4,5)(7.8,7)
\psline(1.6,5)(2.8,7)
\psline(1.6,5)(3.8,7)
\psline(2.4,5)(1.8,7)
\psline(2.4,5)(0.8,7)
\psline(2.4,5)(7.8,7)
\psline(2.6,5)(6.8,7)
\psline(2.4,5)(3.8,7)
\psline(2.6,5)(1.8,7)
\psline(3.4,5)(0,7)
\psline(3.4,5)(4.8,7)
\psline(3.4,5)(5.8,7)
\psline(3.6,5)(2.8,7)
\psline(3.6,5)(6.8,7)
\psline(3.6,5)(4.8,7)
\psline(4.4,5)(7.8,7)
\psline(4.4,5)(5.8,7)

\parametricplot{1.0193196127018804}{2.1204355467391705}{1*5.64*cos(t)+0*5.64*sin(t)+2.54|0*5.64*cos(t)+1*5.64*sin(t)+0.19}
\psline(-0.4,5)(8.8,7)
\psline(8.8,7)(4.4,5)
\psline(8.8,7)(1.6,5)
\parametricplot{0.923831965944893}{2.2128864854712793}{1*7.42*cos(t)+0*7.42*sin(t)+4.03|0*7.42*cos(t)+1*7.42*sin(t)+-0.92}

\begin{scriptsize}
\psdots[dotstyle=*,linecolor=blue](2,1.5)
\psdots[dotstyle=*,linecolor=red](8,1.5)
\psdots[dotstyle=*,linecolor=blue](6.5,3.5)
\psdots[dotstyle=*,linecolor=blue](9.5,3.5)
\psdots[dotstyle=*,linecolor=red](0,3.5)
\psdots[dotstyle=*,linecolor=red](3,3.5)
\psdots[dotstyle=*,linecolor=red](6,5)
\psdots[dotstyle=*,linecolor=red](7,5)
\psdots[dotstyle=*,linecolor=red](5.5,5)
\psdots[dotstyle=*,linecolor=red](4,3.5)
\psdots[dotstyle=*,linecolor=red](2,3.5)
\psdots[dotstyle=*,linecolor=red](1,3.5)
\psdots[dotstyle=*,linecolor=red](6.5,5)
\psdots[dotstyle=*,linecolor=red](7.5,5)
\psdots[dotstyle=*,linecolor=red](9.5,5)
\psdots[dotstyle=*,linecolor=red](9,5)
\psdots[dotstyle=*,linecolor=red](8.5,5)
\psdots[dotstyle=*,linecolor=red](10,5)
\psdots[dotstyle=*,linecolor=red](10.5,5)
\psdots[dotstyle=*,linecolor=blue](4.4,5)
\psdots[dotstyle=*,linecolor=blue](3.6,5)
\psdots[dotstyle=*,linecolor=blue](3.4,5)
\psdots[dotstyle=*,linecolor=blue](2.6,5)
\psdots[dotstyle=*,linecolor=blue](2.4,5)
\psdots[dotstyle=*,linecolor=blue](1.6,5)
\psdots[dotstyle=*,linecolor=blue](1.4,5)
\psdots[dotstyle=*,linecolor=blue](0.6,5)
\psdots[dotstyle=*,linecolor=blue](0.4,5)
\psdots[dotstyle=*,linecolor=blue](-0.4,5)
\psdots[dotstyle=*,linecolor=red](7.8,7)
\psdots[dotstyle=*,linecolor=red](1.8,7)
\psdots[dotstyle=*,linecolor=red](3.8,7)
\psdots[dotstyle=*,linecolor=red](4.8,7)
\psdots[dotstyle=*,linecolor=red](0,7)
\psdots[dotstyle=*,linecolor=red](0.8,7)
\psdots[dotstyle=*,linecolor=red](6.8,7)
\psdots[dotstyle=*,linecolor=red](5.8,7)
\psdots[dotstyle=*,linecolor=red](2.8,7)
\psdots[dotstyle=*,linecolor=red](8.8,7)

\end{scriptsize}
\end{pspicture*}
\caption{Part of the (6,3;6)-cage.}
\label{fig:m5}
\end{center}
\end{figure}

On one hand,
$$n_0(3,5;6)=\left\lceil \frac{2(5)^2+7(5)+3}{3}\right\rceil = 30 \mbox{ and } \left\lceil \frac{5}{3} + \frac{1}{3} \right\rceil =2 \leq e, $$
hence $$32 \leq |V(G)|.$$

On the other hand, it follows from Figure~\ref{fig:m5} that
$$|V(G)|=|V(G')|-2-5=\frac{2(6)^2+7(6)+3}{3}-7=\frac{2(36)+42+3}{3}-7=\frac{117}{3}-7$$
$$|V(G)|=39-7=32,$$
and $G$ is necessarily a cage.

\section {Bipartite biregular  cages of girths 8, 12 and 16}

We close our paper with two results concerning biregular bipartite $(n,m;2r)$-graphs for $r\in\{4,6,12\}$ using the identities given in Theorem \ref{PL}. The first result follows immediately from Lemma~\ref{VMLemma}, Theorem \ref{PL} and the existence results mentioned in the paragraph following these.
It deals with biregular bipartite Moore cages of girths $8,12$ and $16$.
\begin{theorem}\label{bb-cages}
There exist infinite families of biregular bipartite Moore cages with parameters
$(n+1,n^2+1;8)$, $(n+1,n^3+1;12)$ and $(n+1,n^2+1;16)$.
\end{theorem}

Finally, we address the existence of biregular bipartite $(n,m;2r)$-graphs in relation
to the Moore  bound $B(n,m;2r)$ (\ref{Moore:bound-even}) and (\ref{Moore:bound-odd}) proved in
\cite{FilRamRivJaj19}. The idea behind the proof included in \cite{FilRamRivJaj19}
is to consider a tree denoted by ${\cal{T}}_{uv}$ whose order matches the Moore
bound $B(n,m;2r)$ and is called the {\em{Moore tree}}.
It is necessarily contained in any biregular bipartite $(n,m;2r)$-graph
and consists of trees ${\cal{T}}_u$ and ${\cal{T}}_v$ attached to the vertices $u$
and $v$ of an edge $f=uv$. Each of the two trees consists of levels of vertices of varying degrees $n$ and $m$ and depth $r-1$ (one starting of a root of degree $n-1$ and one starting of a root of degree $m-1$, and the last level consisting of vertices of degree $1$).
Thus, ${\cal{T}}_{uv}$ is the union of an edge $f=uv$ and two disjoints trees ${\cal{T}}_u$ and ${\cal{T}}_v$, rooted in $f=uv$, where $V({\cal{T}}_{uv})=V({\cal{T}}_u)\cup V({\cal{T}}_v)$ and $E({\cal{T}}_{uv})=E({\cal{T}}_u)\cup E({\cal{T}}_v)\cup f$. A biregular bipartite $(n,m;2r)$-Moore cage exists if and only if
the tree ${\cal{T}}_{uv}$ can be completed into an $(n,m;2r)$-graph by adding
$n-1$ edges to each leaf of ${\cal{T}}_u$ connecting these leaves
to the leaves of the tree ${\cal{T}}_v$ in such a way that that each leave of
${\cal{T}}_v$ ends up being of degree $m$ and no cycles shorter than $2r$ are introduced.

Using techniques introduced in the study of the $(k;g)$-cage problem (see for example \cite{AGMS07,ABGMV08,ABH10}), we obtain the following extension of
Theorem~\ref{bb-cages} to other classes of parameters $(n,m;2r)$.
\begin{theorem}
There exist infinite families of biregular bipartite $(n,m;2r)$-graphs
with parameters $m=n^2$ for $r= \{4,8\}$, and  $m=n^3$ for $r=6$, whose orders
are
\[ n^{\frac{r}{2}}m^{\frac{r}{2}-1}+m^{\frac{r}{2}}n^{\frac{r}{2}-1}. \]
\end{theorem}

\begin{proof}
Let $G$ be a biregular bipartite Moore $(n+1,m+1;2g)$-cage whose existence is
guaranteed by Theorem~\ref{bb-cages}. As argued above, the Moore graph $G$ contains the Moore tree ${\cal{T}}_{uv}$ with the additional edges connecting the
leaves of the two subtrees ${\cal{T}}_u$ and ${\cal{T}}_v$. Deleting the edges and vertices of ${\cal{T}}_{uv}$ other than the leaves and the edges connecting them
yields a bipartite biregular graph with the desired parameters.
\end{proof}

We do not know whether the graphs constructed in the proof of the above theorem are cages or not.


\section{Introduction}
Estimating the mean of a random vector based on independent and
identically distributed samples is one of the most basic
statistical problems. In the last few years the problem has attracted
a lot of attention and important advances have been made both in terms
of statistical performance and computational methodology.

In the simplest form of the mean estimation problem, one wishes to
estimate the expectation $\mu = \mathbb{E} X$ of a random vector
$X$ taking values in $\mathbb{R}^d$, based on a sample $X_1,\ldots,X_N$
consisting of independent copies of $X$. An \emph{estimator} is a
(measurable) function of the data
$$
\widehat{\mu} = \widehat{\mu}(X_1,\ldots,X_N) \in \mathbb{R}^d~.
$$
We measure the quality of an estimator by the distribution of its
Euclidean distance to the mean vector $\mu$. More precisely,
for a given $\delta >0$---the \emph{confidence parameter}---, one would like to ensure that
$$
\|\widehat{\mu} - \mu\| \leq \varepsilon(N,\delta) \ \ {\rm with \ probability \ at \ least \ } 1-\delta
$$
with $\varepsilon(N,\delta)$ as small as possible. Here and in the entire
article, $\|\cdot\|$ denotes the Euclidean norm in $\mathbb{R}^d$.

The obvious choice of $\widehat{\mu}$ is the empirical mean
$N^{-1}\sum_{i=1}^N X_i$, which, apart from its
computational simplicity, has good statistical properties when the
distribution is sufficiently well-behaved.
However, it is well known that, even when $X$ is real valued, the
empirical mean behaves sub-optimally and much better mean estimators
are available\footnote{We refer the reader to the recent survey \cite{LuMe19} for an extensive discussion.}. The reason for the
suboptimal performance of the empirical mean is the damaging effect of \emph{outliers} that are inevitably present when the distribution is heavy-tailed.

Informally put, outliers are sample points that are, in some sense,
atypical; as a result they cause a significant distortion to the
empirical mean. The crucial fact is that when $X$ is a heavy-tailed random variable, a typical sample contains a significant number of outliers, implying the empirical mean is likely to be distorted.

To exhibit the devastating effect that outliers cause, let $\varepsilon>0$ and
note that there is a square integrable (univariate) random variable $X$ such that
$$
\left|\frac{1}{N}\sum_{i=1}^N X_i - \mu \right| \geq \varepsilon \ \ \ {\rm
  with \ probability \ at \ least} \ c \frac{\sigma_X^2}{\varepsilon^2 N}
$$
for a positive absolute constant $c$; $\sigma_X^2$ is the
variance of $X$.
In other words, the best possible error $\varepsilon(N,\delta)$   that can be guaranteed by the
empirical mean (when only finite variance is assumed)
is of the order of
$\sigma_X/\sqrt{\delta N}$.
On the other hand, it is well known (see, e.g., the survey
\cite{LuMe19})
that there are estimators of the mean $\widehat{\mu}$ such that for all square-integrable random variables $X$,
\begin{equation} \label{eq:intro-opt-single}
|\widehat{\mu}-\mu| \leq c\sigma_X \sqrt{\frac{\log(2/\delta)}{N}} \ \ \ {\rm with \ probabilty \ } 1-\delta
\end{equation}
where $c$ is a suitable absolute constant.
An estimator that performs with an error $\varepsilon(N,\delta)$ of the
order of $\sigma_X \sqrt{\log(2/\delta)/N}$ is called a
sub-Gaussian estimator.
Such estimators are optimal in the sense that no estimator can perform with a better error $\varepsilon(N,\delta)$ even if $X$ is known to be a Gaussian random variable.

Because the empirical mean is such a simple estimator and
seeing that outliers are the probable cause of its sub-optimality,
for real-valued random variables, a natural attempt to improve the performance of the empirical mean is
removing possible outliers using a truncation of $X$. Indeed, the
so-called \emph{trimmed-mean} (or \emph{truncated}-mean) estimator
 is defined by removing a fraction of the sample,
consisting of the $\gamma N$ largest and smallest points for some
parameter $\gamma \in (0,1)$, and then averaging over the rest.
This idea is one of the most classical tools in robust statistics and
we refer to  Tukey and McLaughlin \cite{TuMc63}, Huber and Ronchetti
\cite{HuRo09}, Bickel \cite{Bic65}, Stigler \cite{Sti73} for early
work on the theoretical properties of the trimmed-mean estimator.
However, the non-asymptotic sub-Gaussian
property of the trimmed mean was established only recently, by Oliveira and Orenstein in \cite{OlOr19}. They proved that if $\gamma = \kappa \log(1/\delta)/N$
for a constant $\kappa$,  then the trimmed mean estimator $\widehat{\mu}$
satisfies (\ref{eq:intro-opt-single}) for all distributions with a
finite variance $\sigma_X$ and with a constant $c$ that depends on
$\kappa$ only.

An added value of the trimmed mean is that it seems to be robust to malicious noise, at least intuitively. Indeed, assume that an
adversary can
corrupt $\eta N$ of the $N$ points for some $\eta <1$. The trimmed-mean estimator can
withstand at least one sort of contamination: the adversary making the
corrupted points either very large or very small. This does not rule
out other damaging changes to the sample, but at least it gives the
trimmed mean another potential edge over other estimators.
And, in fact, as we prove in this article, the performance of the
trimmed-mean estimator is as good as one can hope for
under both heavy-tailed distributions and adversarial corruption.
We show that---a simple variant of---the trimmed-mean estimator
achieves
\begin{equation} \label{eq:intro1}
   |\widehat{\mu} - \mu| \le c\sigma_X \left(\sqrt{\eta} +
     \sqrt{\frac{\log(1/\delta)}{N}} \right)
\end{equation}
with probability $1-\delta$, for an absolute constant $c$
(see Theorem \ref{thm:trimmed-mean-dim-1} for the detailed statement).
The bound \eqref{eq:intro1} holds for all univariate distributions with a finite variance, and is minimax optimal in that
class of distributions. For distributions with lighter tail, the
dependence  on the contamination level $\eta$ can be improved.
For example, for sub-Gaussian distributions $\sqrt{\eta}$ may be
replaced by $\eta\sqrt{\log(1/\eta)}$ and the trimmed-mean estimator
achieves that. As we explain in what follows, the parameter $\gamma$ that determines the level of trimming depends on the confidence parameter $\delta$ and contamination level $\eta$ only.

The problem of mean estimation in the multivariate case (i.e., when
$X$ takes values in $\R^d$ for some $d>1$) is considerably more
complex. For i.i.d.\ data without contamination, the best possible statistical performance for square-integrable random vectors is well understood:
if $\Sigma=\mathbb{E} \left[(X-\mu)(X-\mu)^T  \right]$ is the covariance
matrix of $X$ whose largest eigenvalue and trace are denoted by
$\lambda_1$ and $\mathrm{Tr}(\Sigma)$, respectively, then for every
$\delta>0$, there exists a mean estimator $\widehat{\mu}$ such that,
regardless of the distribution, with probability at least $1-\delta$,
\begin{equation}
\label{eq:subgaussiid}
   \|\widehat{\mu} - \mu\| \le c\left( \sqrt{\frac{\mathrm{Tr}(\Sigma)}{N}} +
       \sqrt{\frac{\lambda_1\log(1/\delta)}{N}} \right)
\end{equation}
for some absolute constant $c$. This bound is optimal in the sense
that one cannot improve it even when the distribution is known to be
Gaussian. The existence of such a ``sub-Gaussian'' estimator was
established by Lugosi and Mendelson \cite{LuMe16a}. Computationally
efficient versions have been subsequently constructed by Hopkins
\cite{Hop18} and by Cherapanamjeri, Flammarion, and Bartlett
\cite{ChFlBa19}, see also Depersin and Lecu\'e \cite{DeLe19}.
Once again, we refer to the survey \cite{LuMe19} for related results.

A natural question is how well one can estimate the mean of a random
vector in the presence of adversarial contamination. In particular,
one may ask the following:

\begin{tcolorbox}
Let $X$ be a random vector in $\mathbb{R}^d$ whose mean and covariance matrix
exist. Let $X_1,\ldots,X_N$ be i.i.d.\ copies of $X$.
Then the adversary, maliciously (and knowing in advance of
statistician's intentions), is free to change at most $\eta N$
of the sample points. How accurately can $\mu=\mathbb{E} X$ be estimated with
respect to the Euclidean norm?
In particular, given $\delta$ and $\eta$, does there exist an estimator and an absolute constant
$c$ such that, regardless of the distribution of $X$, with probability
at least $1-\delta$,
\begin{equation}
\label{eq:subgauss}
   \|\widehat{\mu} - \mu\| \le c\left( \sqrt{\frac{\mathrm{Tr}(\Sigma)}{N}} +
       \sqrt{\frac{\lambda_1\log(1/\delta)}{N}} + \sqrt{\lambda_1\eta}
     \right)~?
\end{equation}

\end{tcolorbox}

The main result of this article, Theorem \ref{thm:main}, answers this
question in the affirmative. To that end, we construct a
procedure, based on the one-dimensional trimmed-mean estimator,
that has the desired performance guarantees.

\subsection*{Related work}
The model of estimation under adversarial contamination has been
extensively addressed in the literature of computational learning
theory. Its origins may be traced back to the malicious noise model of
Valiant \cite{Val85} and Kearns and Li \cite{KeLi93}. In the context of
mean estimation it has been investigated by
Diakonikolas, Kamath, Kane, Li, Moitra, and Stewart
\cite{DiKaKaLiMoSt16,DiKaKaLiMoSt17,DiKaKaLiMoSt18},
Steinhardt, Charikar, and Valiant \cite{StChVa17}, Minsker \cite{Min18b}.
In particular, in \cite{DiKaKaLiMoSt17} it is shown that when
$N=\Omega((d/\eta)\log d)$ and $\lambda_1$ is the largest eigenvalue
of the covariance matrix $\Sigma$ of $X$, then there exists a
computationally efficient estimator of the mean that satisfies
\[
   \|\widehat{\mu}-\mu\| \le c \sqrt{\lambda_1\eta}
\]
with probability at least $9/10$ for all distributions. Although this bound is sub-optimal in terms of the conditions and does not recover the
sub-Gaussian bounds, the goal in \cite{DiKaKaLiMoSt17}, and in other articles in this direction as well, was mainly on computational efficiency. In contrast, our aim is to construct
an estimator with optimal statistical performance, and the multivariate
estimator we propose is not computationally feasible---at least in its
naive implementation---in the sense that computing the estimator takes
time that is exponential in the dimension. It is an intriguing problem to
find computationally efficient mean estimators that have optimal
statistical performance under the weakest possible assumptions: although
such estimators are available for i.i.d.\ data
from the results of Hopkins \cite{Hop18}
and Cherapanamjeri, Flammarion, and Bartlett \cite{ChFlBa19}, these
estimators
are not expected to perform well under adversarial contamination.

The sub-Gaussian estimators achieving the bound  (\ref{eq:subgaussiid})
are based on median-of-means estimators. Such estimators have been
studied under a (somewhat more restrictive) adversarial contamination model
by Lecu{\'e} and Lerasle \cite{LeLe17a} and by Minsker \cite{Min18b},
see also see Rodriguez and Valdora \cite{RoVa19}.
In particular,
Minsker \cite{Min18b} studies estimators that cleverly combine  Huber's robust
$M$-estimators with the  median-of-means technique. His results imply
a performance bound exactly of the form of (\ref{eq:subgauss}). A
disadvantage  of Minsker's estimator is that it assumes that
the trace and operator norm of the covariance matrix are known up to
a constant factor.

In a recent manuscript, Depersin and Lecu\'e \cite{DeLe19} study the
problem of robust mean estimation a slightly more restrictive model of
contamination. Their main result is a computationally efficient
multivariate mean estimator that achieves a performance similar to
\eqref{eq:subgauss}, though only when $\eta$ is at most a small constant times
$\log(1/\delta)/N$; thus, it is only able to handle low levels of contamination.

Chen, Gao, and Ren \cite{ChGaRe16} develop a general theory of minimax bounds
under Huber's contamination model (i.e., when the contamination is i.i.d.) for parametric families of distributions.
In \cite{ChGaRe18} the same authors study robust estimation of the mean vector and covariance matrix
under Huber's contamination model and derive sharp minimax bounds for Gaussian, and more generally
elliptical, distributions. In particular, they show that if the uncontaminated data is Gaussian with
identity covariance matrix, then Tukey's median $\widehat{\mu}$ satisfies that, with probability at least $1-\delta$,
\[
   \|\widehat{\mu}-\mu\| \le c\left( \sqrt{\frac{d}{N}} +
       \sqrt{\frac{\log(1/\delta)}{N}} + \eta
     \right)~.
\]
Moreover, they prove that this estimator is minimax optimal up to constant factors.
Note that (\ref{eq:subgauss}) has a similar form except that the term $\eta$ is replaced
by the weaker $\sqrt{\eta}$. It is remarkable that this is the only (necessary) price
one has to pay for moving from Gaussian  distributions to arbitrary ones whose covariance matrix exists
and from Huber's contamination to adversarial one.
Moreover, as we argue below, for sub-Gaussian distributions the term $\sqrt{\eta}$ may be improved to
$\eta\sqrt{\log(1/\eta)}$. We also refer to  Dalalyan and Thompson \cite{DaTo19} for recent related work.

The rest of the article is organized as follows. In Section
\ref{sec:dim1} we discuss the univariate case and establish
a performance bound for a version of the trimmed-mean estimator
in Theorem \ref{thm:trimmed-mean-dim-1}. We argue that this bound is
best possible up to the value of the absolute constant.
In Section \ref{sec:multivariate} we extend the discussion to the
multivariate case, and  construct a new estimator.
The proof of the performance bound of the multivariate estimator is
given in Section \ref{sec:proof}.

\section{The real-valued case}
\label{sec:dim1}

Let $X$ be a real-valued random variable that has finite variance $\sigma_X^2$.
Set $\mu = \mathbb{E} X$ and define $\overline{X}=X-\mu$.
In what follows, $c,C$
denote positive absolute constants whose value may change at each appearance.
 For $0<p<1$, define the quantile
\begin{equation}
\label{eq:qunatile}
Q_p(\overline{X}) = \sup \left\{M \in \mathbb{R} : \mathbb{P}\left(\overline{X} \geq M\right) \geq 1-p\right\}~.
\end{equation}
For simplicity of presentation, we assume throughout the
article that $X$ has an absolutely continuous distribution.
Under this assumption, it follows that $\mathbb{P}\left(\overline{X} \geq Q_p(\overline{X})\right) = 1-p$.
However, we
emphasize that this assumption is not restrictive: one may easily
adjust the proof to include all distributions with a finite second moment.
Another solution is that the
statistician can always add a small independent Gaussian noise to the sample points, thus ensuring that the distribution has a density and
without affecting statistical performance.

For reasons of comparison, our starting point is a simple lower bound that limits the performance of
every mean estimator. Similar arguments appear in
\cite{DiKaKaLiMoSt17} and \cite{Min18b}.

While the adversary has total freedom to change at most $\eta N$ of
the sample points,
consider first a rather trivial action: changing the i.i.d.\ sample $(\mathcal{X}_i)_{i=1}^N$ to $(\widetilde{X}_i)_{i=1}^N$ defined by
\begin{equation} \label{eq:trivial-change}
\widetilde{X}_i = \min\{X_i, \mu+Q_{1-\eta/2}(\overline{X})\}~.
\end{equation}
Since
$$
\mathbb{P}\left(\overline{X} \geq Q_{1-\eta/2}(\overline{X})\right) = \frac{\eta}{2}~,
$$
by a binomial tail bound, with probability at least $1-2\exp(-c\eta N)$,
$$
\left|\left\{i: X_i -\mu \geq Q_{1-\eta/2}(\overline{X})\right\}\right| \leq \frac{3}{4}\eta N~.
$$
In particular, on this event, the adversary can change all sample
points $X_i$ that are bigger than $\mu+Q_{1-\eta/2}(\overline{X})$.
As a result, there is no way one can determine whether $(\widetilde{X}_i)_{i=1}^N$ is a corrupted sample, originally selected according to $X$ and then changed as in \eqref{eq:trivial-change}, or an uncorrupted sample selected according to the random variable
$$
Z=\min\left\{X, \mu+Q_{1-\eta/2}(\overline{X})\right\}~.
$$
Therefore, on this event, no procedure can distinguish between $\mathbb{E} X$ and $\mathbb{E} Z$, which means that the error caused by this action is at least $| \mathbb{E} Z - \mu|$. Note that for $M=Q_{1-\eta/2}(\overline{X})$ one has that
\[
| \mathbb{E} Z - \mu | =
 \mathbb{E} \left[ (\overline{X}-M) \mathbbm{1}_{\overline{X} \geq M}\right]~.
\]
Since the adversary can target the lower tail of $X$ in exactly the
same way, it follows that,  with probability at least $1-2\exp(-c\eta N)$, no estimator can perform with accuracy better than
\begin{eqnarray*}
\lefteqn{
\overline{\cal E} (\eta,X)   } \\
& \stackrel{\mathrm{def.}}{=} & \max \left\{\mathbb{E} \left[|\overline{X}-Q_{\eta/2}(\overline{X})| \mathbbm{1}_{\overline{X} \leq Q_{\eta/2}(\overline{X})}\right], \mathbb{E} \left[|\overline{X}-Q_{1-\eta/2}(\overline{X})| \mathbbm{1}_{\overline{X} \geq Q_{1-\eta/2}(\overline{X})} \right] \right\}~.
\end{eqnarray*}
Of course, the adversary has a second trivial action: do nothing. That
is a better corruption strategy (in the minimax sense) when
$$
\overline{\cal E}(\eta,X)  \leq C \sigma_X \sqrt{\frac{\log(2/\delta)}{N}}~.
$$
Therefore, if one wishes to find a procedure that performs with probability at least $1-\delta-2\exp(-c\eta N)$, the best error one can hope for is
\begin{equation} \label{eq:corrupt-error}
\overline{\cal E}(\eta,X) + C \sigma_X\sqrt{\frac{\log(2/\delta)}{N}}~,
\end{equation}
where $c$ and $C$ are absolute constants.

A rather surprising fact is that in the real-valued case, the two trivial actions cause the largest possible damage. Indeed,
we show that there is an estimator that is a simple modification of
trimmed mean that attains what is almost the optimal
error---with $\overline{\cal E}(\eta,X)$ replaced by
$$
{\cal E} (\eta,X)\stackrel{\mathrm{def.}}{=} \max \left\{\mathbb{E} \left[|\overline{X}| \mathbbm{1}_{\overline{X} \leq Q_{\eta/2}(\overline{X})}\right], \mathbb{E} \left[|\overline{X}| \mathbbm{1}_{\overline{X} \geq Q_{1-\eta/2}(\overline{X})} \right] \right\}~.
$$

\noindent {\bf Remark.}\ \
It is straightforward to construct a random variable $X$ for which
$\overline{\cal E}(\eta,X) \geq c_1 \sqrt{\eta}\sigma_X$.
(Take, for example $X$ that takes value $0$ with probability $1-\eta$ and values $\pm\sigma_X/\sqrt{\eta}$
with probability $\eta/2$ each.)
Thus, in terms of $\eta, \sigma_X, \delta$ and $N$, the best minimax error rate that is possible in the corrupted mean estimation problem for real-valued random variables is
$$
c \sigma_X \max\left\{\sqrt{\eta}, \sqrt{\frac{\log(2/\delta)}{N}}\right\}
$$
for a suitable absolute constant $c$.

Next, let us define the modified trimmed-estimator. The estimator splits the data into two
equal parts. Half of the data points are used to determine the truncation
at the appropriate level. The points from the other half are
averaged as is, except for the data points
that fall outside of the estimated quantiles, which are truncated prior to averaging.
For convenience, assume that the
data consists of $2N$ independent copies of the random variable $X$,
denoted by  $X_1,\ldots,X_N,Y_1,\ldots,Y_N$. The statistician has access
to the corrupted sample
$\widetilde{X}_1,\ldots,\widetilde{X}_N,\widetilde{Y}_1,\ldots,\widetilde{Y}_N$,
where at most $2\eta N$ of the sample points have been changed by an adversary.

 For $\alpha \leq \beta$, let
\[
\phi_{\alpha,\beta}(x) =
\begin{cases}
\beta & \mbox{if} \  x > \beta,
\\
x & \mbox{if} \ x \in [\alpha,\beta],
\\
\alpha & \mbox{if} \ x < \alpha,
\end{cases}
\]
and for $x_1,\ldots, x_m \in \mathbb{R}$ let $x_1^* \leq x_2^* \leq \cdots \leq  x_m^*$ be its non-decreasing rearrangement.

With this notation in place, the definition of the estimator is as follows:

\begin{tcolorbox}
{\bf Univariate mean estimator.}
\begin{description}
\item{$(1)$} Consider the corrupted sample
  $\widetilde{X}_1,\ldots,\widetilde{X}_N,\widetilde{Y}_1,\ldots,\widetilde{Y}_N$ as input.
\item{$(2)$} Given the corruption parameter $\eta$ and confidence level $\delta$, set
$$
\varepsilon=8\eta + 12\frac{\log(4/\delta)}{N}~.
$$
\item{$(3)$} Let $\alpha=\widetilde{Y}_{\varepsilon N}^*$ and $\beta=\widetilde{Y}_{(1-\varepsilon) N}^*$ and set
$$
\widehat{\mu} =\frac{1}{N}\sum_{i=1}^N \phi_{\alpha,\beta}(\widetilde{X}_i)~.
$$
\end{description}
\end{tcolorbox}

\begin{theorem} \label{thm:trimmed-mean-dim-1}
Let $\delta \in (0,1)$ be such that $\delta \ge e^{-N}/4$.
Then, with probability at least $1-\delta$,
$$
|\widehat{\mu}-\mu | \leq 3 {\cal E}(4\varepsilon,X)+ 2\sigma_X
  \sqrt{\frac{\log(4/\delta)}{N}}~.
$$
Moreover, with probability at least $1-4\exp(- \varepsilon N/12)$,
$$
|\widehat{\mu}-\mu | \leq 10 \sqrt{\varepsilon} \sigma_X~.
$$
\end{theorem}

\noindent {\bf Remark.}\ \
The necessity of prior knowledge of the confidence parameter
$\delta$ was pointed out (even in the contamination-free case) by
Devroye, Lerasle, Lugosi, and Oliveira \cite{DeLeLuOl16}, see
\cite{LuMe19} for further discussion. The contamination level
need not be known exactly. If an upper bound $\overline{\eta}\ge \eta$ is
available and one uses the estimator with parameter $\overline\eta$ instead
of $\eta$, then the same bound holds with $\eta$ replaced by $\overline{\eta}$.

To explain the meaning of Theorem \ref{thm:trimmed-mean-dim-1}, observe that for $M=Q_{1-\varepsilon/2}(\overline{X})$, one has
$$
\frac{\varepsilon}{2} = \mathbb{P}\left(\overline{X} \geq M\right) \leq \frac{\sigma_X^2}{M^2}~,
$$
and in particular,
\begin{equation}
\label{eq:quantilebound}
Q_{1-\varepsilon/2}(\overline{X}) \leq  \frac{\sigma_X\sqrt{2}}{\sqrt{\varepsilon}}~.
\end{equation}
Also,
\begin{eqnarray}
\label{eq:ebound}
\mathbb{E} \left[(\overline{X}-M) \mathbbm{1}_{\overline{X} \geq M}\right] & \leq  &
\mathbb{E}\left[|\overline{X}| \mathbbm{1}_{\overline{X} \geq M} \right]+ \mathbb{E} \left[M \mathbbm{1}_{\overline{X} \geq M} \right]
\nonumber \\
& \leq  &
\sigma_X \mathbb{P}^{1/2}(\overline{X} \geq M) + |M| \mathbb{P}(\overline{X} \geq M)
\nonumber \\
& \leq &
\sigma_X\sqrt{8\varepsilon}~,
\end{eqnarray}
implying that for every $X$,
\begin{equation} \label{eq:upper-error-intro}
{\cal E}(\varepsilon,X) \leq \sigma_X\sqrt{8\varepsilon}~.
\end{equation}
 Hence, Theorem \ref{thm:trimmed-mean-dim-1} shows that the
 estimator attains the minimax rate
of the corrupted mean-estimation problem, noted previously.

Of course, Theorem \ref{thm:trimmed-mean-dim-1} actually implies sharper individual bounds: if $\eta N \leq \log(2/\delta)$, then $\varepsilon \sim N^{-1} \log(2/\delta)$ and the assertion of Theorem \ref{thm:trimmed-mean-dim-1} is that, with probability at least $1-\delta$,
$$
|\widehat{\mu}-\mu | \le C \sigma_X \sqrt{\frac{\log(2/\delta)}{N}}~,
$$
which matches the optimal sub-Gaussian error rate. If, on the other hand, $\eta N > \log(2/\delta)$, then with probability at least $1-\delta$,
$$
|\widehat{\mu}-\mu | \le C {\cal E}(c\eta, X)~,
$$
essentially matching the lower bound (\ref{eq:corrupt-error}).

\noindent {\bf Remark.}\ \
Observe that the upper bound
on
 ${\cal E}(\varepsilon,X)$ in
\eqref{eq:upper-error-intro} is based only on $\sigma_X$, and
therefore on the fact that $X$ is square-integrable. Under stronger
moment assumptions on $X$, an improved bound can be easily
established. For example, if $X$ is sub-Gaussian, that is, if for
every  $p \geq 2$, $\left(\mathbb{E} |\overline{X}|^p\right)^{1/p} \leq c \sqrt{p}
\sigma_X$,
the same argument used in \eqref{eq:upper-error-intro} for $p=\log(1/\varepsilon)$ shows that
$$
2{\cal E}(4\varepsilon,X)  + \frac{\varepsilon}{2} \max\{|Q_{\varepsilon/2}(\overline{X})|, |Q_{1-\varepsilon/2}(\overline{X})|\} \leq c \varepsilon \sqrt{\log(1/\varepsilon)} \sigma_X~.
$$

One may wonder if $\eta \sqrt{\log(1/\eta)}$ is the correct order of dependence
on the contamination level for sub-Gaussian distributions.
As it is proved by Chen, Gao, and Ren \cite{ChGaRe18},
if $X$ is Gaussian and the contamination comes from Huber's model,
the correct dependence on the contamination level is proportional to $\eta$, suggesting
a possible slight improvement.
At the same time, as we discuss it above, $\overline{\mathcal{E}}(\eta,X)$ is a lower bound for any estimator.
One may easily check that, if $X$ is Gaussian, $\overline{\mathcal{E}}(\eta,X)$ is of the order of
 $\eta /\sqrt{\log(1/\eta)}$ so this lower bound is loose in this case.
Interestingly, however, there exist sub-Gaussian distributions under which
$\overline{\mathcal{E}}(\eta,X)$ is of the order of $\eta \sqrt{\log(1/\eta)}$.
(As an example, one may take $X=\mathbbm{1}_{|G| \le Q} \min(1,|G|) + \mathbbm{1}_{|G| > Q} |G|$ where $G$ is a standard
Gaussian random variable and $Q$ is its $1-\eta/2$ quantile.)
This means that for
sub-Gaussian distributions, the upper bound of Theorem 1 is indeed tight, up to constant
factors.
Note that our lower bound uses the adversarial nature of the contamination, so
it might be the case that under Huber's model, even for sub-Gaussian distributions,
$\eta$ is the correct order.

\subsection{Proof of Theorem \ref{thm:trimmed-mean-dim-1}}

Recall that one is given the corrupted sample $\widetilde{X}_1,\ldots,\widetilde{X}_N,\widetilde{Y}_1,\ldots,\widetilde{Y}_N$, out of which at most $2\eta N$ of the sample points have been corrupted. Also, $(z_i^*)_{i=1}^N$ denotes a \emph{non-decreasing} rearrangement of the sequence $(z_i)_{i=1}^N$.

The first step of the estimation procedure determines the
truncation level, which is done using the first half of the
corrupted sample.

Consider the corruption-free sample $Y_1,\ldots,Y_N$ and let
$U=\mathbbm{1}_{\overline{X} \geq Q_{1-2\varepsilon}(\overline{X}) }$. Since $X$ is
absolutely continuous,
we have that $\mathbb{P}\left(\overline{X} \geq Q_{1-2\varepsilon}(\overline{X})\right)=2\varepsilon$ and
$$
\sigma_U \leq \mathbb{P}^{1/2}(\overline{X} \geq Q_{1-2\varepsilon}(\overline{X})) = (2\varepsilon)^{1/2}~.
$$
A straightforward application of Bernstein's inequality shows that, with probability at least $1-\exp(-\varepsilon N/12)$,
\begin{equation} \label{eq:E1}
\left|\{i : Y_i \geq \mu + Q_{1-2\varepsilon}(\overline{X})\}\right| \geq \frac{3}{2}\varepsilon N~.
\end{equation}
A similar argument for $U=\mathbbm{1}_{\overline{X}  > Q_{1-\varepsilon/2}(\overline{X}) }$ implies that, with probability at least $1-\exp(-\varepsilon N/12)$,
\begin{equation} \label{eq:E2}
\left|\{i : Y_i \leq \mu + Q_{1-\varepsilon/2}(\overline{X})\}\right| \geq (1-(3/4)\varepsilon) N~.
\end{equation}
Similarly, with probability at least $1-2\exp(-\varepsilon N/12)$,
\begin{equation} \label{eq:E3}
\left|\{i : Y_i \leq \mu + Q_{2\varepsilon}(\overline{X})\}\right| \geq \frac{3}{2}\varepsilon N~,
\end{equation}
and, with probability at least $1-2\exp(-\varepsilon N/12)$,
\begin{equation} \label{eq:E4}
\left|\{i : Y_i \geq \mu + Q_{\varepsilon/2}(\overline{X})\}\right| \geq (1-(3/4)\varepsilon) N~.
\end{equation}
Thus, with probability at least $1-4\exp(-\varepsilon N/12)\ge 1-\delta/2$, \eqref{eq:E1}--\eqref{eq:E4} hold simultaneously on an event we denote by $E$. Importantly, the event $E$ only depends on the uncorrupted sample $Y_1,\ldots,Y_N$.

Since $\eta \le \epsilon/8$, following any corruption of at most $2\eta N$ points, on the event $E$
$$
\left|\{i : \widetilde{Y}_i \geq \mu + Q_{1-2\varepsilon}(\overline{X})\}\right| \geq \left((3/2)\varepsilon-2\eta\right) N \geq \varepsilon N
$$
and
$$
\left|\{i : \widehat{Y}_i \leq \mu + Q_{1-\varepsilon/2}(\overline{X})\}\right| \geq (1-(3/4)\varepsilon-2\eta) N \geq (1-\varepsilon) N~;
$$
in other words,
\begin{equation}\label{eq:beta-single}
Q_{1-2\varepsilon}(\overline{X}) \leq \widetilde{Y}_{(1-\varepsilon) N}^* - \mu \leq  Q_{1-\varepsilon/2}(\overline{X})~.
\end{equation}
Similarly, on the event $E$, we also have
\begin{equation} \label{eq:alpha-single}
Q_{\varepsilon/2}(\overline{X}) \leq \widetilde{Y}_{\varepsilon N}^*-\mu \leq Q_{2\varepsilon}(\overline{X})~.
\end{equation}
Recall that the truncation levels are
\[
\alpha=\widetilde{Y}_{\varepsilon N}^* \ \ \ {\rm and } \ \ \ \beta=\widetilde{Y}_{(1-\varepsilon) N}^*~.
\]
To prove Theorem \ref{thm:trimmed-mean-dim-1},
first we show that $(1/N)\sum_{i=1}^N \phi_{\alpha,\beta}(X_i)$
satisfies an inequality of the wanted form, and then we prove that
corruption does not change the empirical mean of
$\phi_{\alpha,\beta}$ by too much; that is, that
$$
\left| \frac{1}{N} \sum_{i=1}^N \phi_{\alpha,\beta}(X_i) - \frac{1}{N} \sum_{i=1}^N \phi_{\alpha,\beta}(\widetilde{X}_i) \right|
$$
is also small enough.

For the first step, note that on the event $E$,
\begin{eqnarray}
\label{eq:sum-decomp}
   \frac{1}{N} \sum_{i=1}^N \phi_{\alpha,\beta}(X_i)
& \le &
\frac{1}{N} \sum_{i=1}^N \phi_{\mu+Q_{2\epsilon}(\overline{X}),\mu+Q_{1-\epsilon/2}(\overline{X})}(X_i)    \\
\nonumber
& = &
\mathbb{E} \phi_{\mu+Q_{2\epsilon}(\overline{X}),\mu+Q_{1-\epsilon/2}(\overline{X})}(X) \\
& &
\nonumber
+
\frac{1}{N} \sum_{i=1}^N \left( \phi_{\mu+Q_{2\epsilon}(\overline{X}),\mu+Q_{1-\epsilon/2}(\overline{X})}(X_i) - \right. \\
& &
\nonumber
 \qquad \left.
\mathbb{E} \phi_{\mu+Q_{2\epsilon}(\overline{X}),\mu+Q_{1-\epsilon/2}(\overline{X})}(X) \right)~.
\end{eqnarray}
The first term on the right-hand side of \eqref{eq:sum-decomp} is bounded by
\begin{eqnarray*}
\mathbb{E} \phi_{\mu+Q_{2\epsilon}(\overline{X}),\mu+Q_{1-\epsilon/2}(\overline{X})}(X)
& \leq &  \mu +
\mathbb{E} \left[\overline{X} \mathbbm{1}_{\overline{X} \geq
         Q_{1-\varepsilon/2}(\overline{X})} \right] \\
& \le &  \mu +{\cal E}(\varepsilon,X)~.
\end{eqnarray*}
On the other hand, since
\begin{eqnarray*}
\mathbb{E} \phi_{\mu+Q_{2\epsilon}(\overline{X}),\mu+Q_{1-\epsilon/2}(\overline{X})}(X)
& \geq &  \mu -
\mathbb{E} \left[\overline{X} \mathbbm{1}_{\overline{X} \leq
         Q_{2\varepsilon}(\overline{X})} \right] \\
& \ge &  \mu -{\cal E}(4\varepsilon,X)~,
\end{eqnarray*}
the second term on the right-hand side of \eqref{eq:sum-decomp}
 is a sum of centered i.i.d.\ random variables (independent of $E$) that are upper bounded
by $Q_{1-\varepsilon/2}(\overline{X})+{\cal E}(4\varepsilon,X)$ and whose
variance
is at most $\sigma_X^2$. Therefore, by Bernstein's inequality, conditioned on $Y_1,\ldots,Y_n$,
 with probability at least $1-\delta/4$,
\begin{eqnarray*}
\lefteqn{
\frac{1}{N} \sum_{i=1}^N \phi_{\alpha,\beta}(X_i) }  \\
& \leq &
\mu +{\cal E}(\varepsilon,X)  +
\sigma_X \sqrt{\frac{2\log(4/\delta)}{N}}
                                                           +\frac{Q_{1-\varepsilon/2}(\overline{X})\log(4/\delta)}{N}
+\frac{{\cal E}(4\varepsilon,X) \log(4/\delta)}{N}  \\
& \le & \mu +2{\cal E}(4\varepsilon,X)  +
2\sigma_X \sqrt{\frac{\log(4/\delta)}{N}}~,
\end{eqnarray*}
where we used the fact that by \eqref{eq:quantilebound},
$Q_{1-\varepsilon/2}(\overline{X}) \log(4/\delta)/N\le \sigma_X
\sqrt{\frac{\log(4/\delta)}{6N}}$ and that ${\cal E}(4\varepsilon,X)
\log(4/\delta)/N \le {\cal E}(4\varepsilon,X)$ by the assumption that $\delta
\ge e^{-N}/4$.

An identical argument for the lower tail shows that, on the event
$E$, with probability at least $1-\delta/2$,
\begin{eqnarray*}
\left| \frac{1}{N} \sum_{i=1}^N \phi_{\alpha,\beta}(X_i) - \mu \right|  & \leq &
2{\cal E}(4\varepsilon,X)  + 2\sigma_X \sqrt{\frac{\log(4/\delta)}{N}}~.
\end{eqnarray*}
It remains to show that, on the event $E$,
\[
\left| \frac{1}{N} \sum_{i=1}^N \phi_{\alpha,\beta}(X_i) - \frac{1}{N} \sum_{i=1}^N \phi_{\alpha,\beta}(\widetilde{X}_i) \right|
\]
is small.
Since $\phi_{\alpha,\beta}(X_i) \not = \phi_{\alpha,\beta}(\widetilde{X}_i)$ for at most $2\eta N$ indices, and for such points that maximal gap is
$$
|\phi_{\alpha,\beta}(X_i) - \phi_{\alpha,\beta}(\widetilde{X}_i)| \leq
|Q_{\varepsilon/2}(\overline{X})| +|Q_{1-\varepsilon/2}(\overline{X})|~,
$$
it follows that
\begin{eqnarray*}
\left| \frac{1}{N} \sum_{i=1}^N \phi_{\alpha,\beta}(X_i) - \frac{1}{N}
  \sum_{i=1}^N \phi_{\alpha,\beta}(\widetilde{X}_i) \right|
& \leq &
2\eta \left( |Q_{\varepsilon/2}(\overline{X})|+ |Q_{1-\varepsilon/2}(\overline{X})|\right)  \\
& \le &
 \frac{\varepsilon}{2} \max\{|Q_{\varepsilon/2}(\overline{X})|, |Q_{1-\varepsilon/2}(\overline{X})|\}~,
\end{eqnarray*}
since $\eta \leq \varepsilon/8$.
Finally, note that
\[
\frac{\varepsilon}{2} Q_{1-\varepsilon/2}(\overline{X})= \mathbb{E} \left[Q_{1-\varepsilon/2}(\overline{X}) \mathbbm{1}_{\overline{X} \geq
         Q_{1-\varepsilon/2}(\overline{X})} \right]\le
\mathbb{E} \left[\overline{X} \mathbbm{1}_{\overline{X} \geq
          Q_{1-\varepsilon/2}(\overline{X})} \right]~,
 \]
and therefore, on the event $E$, we have
\[
  \left| \frac{1}{N} \sum_{i=1}^N \phi_{\alpha,\beta}(X_i) - \frac{1}{N}
  \sum_{i=1}^N \phi_{\alpha,\beta}(\widetilde{X}_i) \right| \le {\cal E}(\varepsilon,X)~.
\]
The second statement of the theorem now follows by \eqref{eq:upper-error-intro}.
{\mbox{}\nolinebreak\hfill\rule{2mm}{2mm}\par\medbreak}

\section{Robust multivariate mean estimation}
\label{sec:multivariate}

In this section we present the main findings of the article: we
construct a multivariate version of the robust mean estimator
and establish the corresponding performance bound announced
in the introduction.

As one may expect, the procedure in the multi-dimensional case is
significantly more involved than in dimension one.
In what follows, $X$ is a random vector taking values in $\mathbb{R}^d$ with mean $\mu = \mathbb{E}
X$ and  covariance matrix of $\Sigma$.  As before, we write $\overline{X}=X-\mu$,
$\lambda_1$ denotes the
largest eigenvalue of $\Sigma$, and $\mathrm{Tr}(\Sigma)= \mathbb{E}
\left\|\overline{X}\right\|^2$ is its trace.

Recall that a
mean estimator receives as data a sample $(\widetilde{X}_i)_{i=1}^N$ that an
adversary fabricates by corrupting at most $\eta N$ points of a
sample $X_1,\ldots,X_N$ of independent, identically distributed
copies of the random vector $X$. As in the univariate case, the estimator requires knowledge of
the contamination level $\eta$ and the confidence parameter $\delta$.
Once again, for clarity of the presentation, we assume that $X$ has an
absolutely continuous distribution with respect to the Lebesgue
measure.

\begin{theorem} \label{thm:main}
Assume that $X$ is a random vector in $\R^d$ that has a mean and
covariance matrix.
There exists a mean estimator $\widehat\mu$
that takes the parameters $\delta\in (0,1),\eta \in [0,1)$
and the contaminated
data $(\widetilde{X}_i)_{i=1}^N$ as input, and satisfies that,
with probability at least $1-\delta$,
$$
\|\widehat{\mu}-\mu\| \leq c \left(\sqrt{\frac{\mathrm{Tr}(\Sigma)}{N}}
  +\sqrt{\frac{\lambda_1\log(1/\delta)}{N}} + \sqrt{\lambda_1\eta}\right)~,
$$
where $c>0$ is a numerical constant.
\end{theorem}

A value of the numerical constant is explicitly given in the
proof. However, no attempt has been made to optimize its value.

The same remark as in the univariate case  on the previous knowledge
of $\eta$ and $\delta$, mentioned after Theorem
\ref{thm:trimmed-mean-dim-1}, applies here as well.

As it is pointed out in the introduction, the bound of Theorem
\ref{thm:main} coincides with the best possible bound in the
corruption-free case up to the term $\sqrt{\lambda_1\eta}$ that is
the price one has to pay for adversarial corruption.
The fact that the term $\sqrt{\lambda_1\eta}$ is inevitable in the
upper bound follows from the fact that for
any upper bound for the norm of difference $\|\widehat\mu -\mu\|$, the same
upper bound holds for
any one-dimensional marginal. Hence, the necessity of this term follows from our
arguments in the univariate case.
At the same time, similarly to the univariate case,
under higher moment assumptions, the term $\sqrt{\lambda_1 \eta}$
may be improved. For instance, if the distribution is sub-Gaussian (in the sense that all one-dimensional
projections are sub-Gaussian), then
this term may be replaced by $\eta \sqrt{\log(1/\eta)} \sqrt{\lambda_1} $.
This may be seen by a straightforward modification of the proof.

Remarkably,
the malicious sample corruption affects only the ``weak'' term of the
bound, that is, it scales with the square root of the operator norm of
the covariance matrix. Indeed, if the corruption parameter $\eta$ is
such that $\eta N \leq \log(2/\delta)$, then, with probability at least $1-\delta$, $\widehat{\mu}$ satisfies
\begin{equation} \label{eq:low-corruption-intro}
\|\widehat{\mu}-\mu\| \leq c \left(\sqrt{\frac{\mathrm{Tr}(\Sigma)}{N}} + \sqrt{\lambda_1} \sqrt{\frac{\log(1/\delta)}{N}}\right)~,
\end{equation}
matching the optimal bound for multivariate mean estimation bound from
\cite{LuMe16a} for the corruption-free case.
If, on the other hand, the corruption parameter is larger, then Theorem \ref{thm:main} implies that with probability at least $1-2\exp(-\eta N/c)$,
\begin{equation} \label{eq:high-corruption-intro}
\|\widehat{\mu}-\mu\| \leq c \left(\sqrt{\frac{\mathrm{Tr}(\Sigma)}{N}} + \sqrt{\eta} \sqrt{\lambda_1} \right)
\end{equation}
for a numerical constant $c>0$.

In what follows we describe the construction of the mean
estimator $\widehat\mu$ that satisfies the announced performance bound.

\subsection{The multivariate mean estimator}

The main component is a mean estimation procedure that, in order to
perform well, requires information on $\mathrm{Tr}(\Sigma)$ and
$\lambda_1$. Since such information is not assumed to be available,
we produce an estimator depending on a tuning parameter $Q$.
Then we
use a simple mechanism of choosing
the appropriate value of $Q$.

Just like in the univariate case, for simplicity of
notation, assume that the estimator receives $2N$ data points
$\widetilde{X}_1,\ldots,\widetilde{X}_N,\widetilde{Y}_1,\ldots,\widetilde{Y}_N$, and that at most $2\eta N$ points of the original independent
sample
$X_1,\ldots,X_N,Y_1,\ldots,Y_N$ have been changed by the adversary.
The procedure computes, for each unit vector $v$ and tuning parameter
$Q>0$,
the trimmed mean
estimate of the expectation of the projection of $X$ to the line
spanned by $v$ with a minor difference: the truncation level is
widened depending on the parameter $Q$. Each one of these estimators defines a slab in $\R^d$. The details are as follows:

\begin{tcolorbox}
{\bf Multivariate mean estimator.}
 \begin{description}
\item{$(1)$}
Set
$$
\varepsilon=\max\left( 10\eta,  2560\frac{\log(2/\delta)}{N}\right)~.
$$

\item{$(2)$} Let $S^{d-1}$ be the Euclidean unit sphere in $\mathbb{R}^d$ and for every $v \in S^{d-1}$ define
$$
\alpha_v = \left(\inr{\widetilde{Y}_i,v}\right)_{(\varepsilon/2)N}^* \quad {\rm and} \quad \beta_v=\left(\inr{\widetilde{Y}_i,v}\right)_{(1-\varepsilon/2)N}^*~.
$$
\item{$(3)$} For every $v \in S^{d-1}$ and $Q>0$, set
$$
U_Q(v)=\frac{1}{N} \sum_{i=1}^N \phi_{\alpha_v-Q,\beta_v+Q}\left(\inr{\widetilde{X}_i,v}\right)~,
$$
and let
$$
\Gamma(v,Q) = \left\{ x \in \mathbb{R}^d : |\inr{x,v}-U_Q(v)| \leq 2\varepsilon
  Q\right \}~.
$$

\item{$(4)$} For each $Q>0$, set
$$
\Gamma(Q)= \bigcap_{v \in S^{d-1}} \Gamma(v,Q)~.
$$

\item{$(5)$} Let $i^* \in \mathbb{Z}$ be the smallest such that
$\bigcap_{i \geq i^*} \Gamma(2^i) \neq \emptyset$. Define $\widehat{\mu}$ to be any point in
\[
     \bigcap_{i\in \mathbb{Z}: i \geq i^*}  \Gamma(2^i)~.
\]
\end{description}
\end{tcolorbox}

Each set $\Gamma(Q)$ is an intersection of random slabs, one for each
direction in the sphere $S^{d-1}$. The ``center'' of the slab
associated with the direction $v$ is $U_Q(v)$ and its width is
proportional to $\varepsilon Q$. As we show in what follows, there is some $i_0 \in \mathbb{Z}$ such that with probability at least $1-\delta$, the sets $\Gamma(2^i), \ i \geq i_0$ are nested, implying that $\widehat{\mu}$ is well-defined.
Note that the last step of selecting the value of $Q$ is reminiscent of
Lepski's method \cite{Lep91} or the related method ``intersection of confidence intervals''  by Goldenshluger and Nemirovski \cite{GoNe97}.

\section{Proof of Theorem \ref{thm:main}}
\label{sec:proof}

The heart of the proof of Theorem \ref{thm:main} is the following
proposition that describes the performance
of an estimator with the correct tuning parameter $Q$.

The role of $Q$ is to incorporate the ``global complexity" of
$S^{d-1}$. In particular, if $Q$ is selected properly, that is enough
to ensure that $\Gamma(Q)$ is nonempty and contains a good estimator
of $\mu$. This is formalized in the next proposition.

\begin{proposition} \label{thm:main-vector}
Let
\begin{equation}  \label{eq:choice-of-Q}
Q_0=
\max\left(\frac{256}{\varepsilon}\sqrt{\frac{\mathrm{Tr}(\Sigma)}{N}}, 16\sqrt{\frac{\lambda_1}{\varepsilon}} \right)
\end{equation}
and consider $Q \in [2Q_0,4Q_0]$. Then, with probability at least $1-2\exp(-\varepsilon N/2560) \geq 1-\delta$, $\Gamma(Q) \not = \emptyset$ and for every $z \in \Gamma(Q)$,
$$
\|z-\mu\| \leq 4 \varepsilon Q_0~.
$$
\end{proposition}

Observe that for every $Q$, the diameter of $\Gamma(Q)$ is at most
$4\varepsilon Q$.
Indeed, if $x_1,x_2 \in \Gamma(Q)$ then for every $v \in S^{d-1}$,
$$
|\inr{x_1-x_2,v}|=|\inr{x_1,v}-\inr{x_2,v}| \leq |\inr{x_1,v}-U_Q(v)|+|\inr{x_2,v}-U_Q(v)| \leq 4\varepsilon Q~,
$$
implying that $\|x_1-x_2\| \leq 4 \varepsilon Q$.

The key component in the proof of Proposition \ref{thm:main-vector} is the next lemma.
\begin{lemma} \label{lemma:uniform-cutoff}
For each $i\in \{1,\ldots,N\}$ and $v\in S^{N-1}$, define $\overline{Y}_i(v)=\inr{Y_i-\mu,v}$.
With probability at least $1-\exp(-\varepsilon N/2560) \geq 1-\delta/2$,
\begin{equation} \label{eq:uniform-beta}
\sup_{v \in S^{d-1}} \left|\left\{i : \overline{Y}_i(v) \geq Q_0\right\}\right| \leq
\frac{\varepsilon}{8}N
\quad \text{and} \quad
\sup_{v \in S^{d-1}} \left|\left\{i : \overline{Y}_i(v) \leq - Q_0\right\}\right| \leq \frac{\varepsilon}{8}N~.
\end{equation}
\end{lemma}

Lemma \ref{lemma:uniform-cutoff} is a uniform version of the analogous claim used in the univariate case.

\medskip

\noindent {\bf Proof.}\ \
Let us prove the first inequality; the second is proved by an identical argument and is omitted.
Consider the function $\chi: \mathbb{R}\to \mathbb{R}$, defined by
\[
   \chi(x) = \left\{ \begin{array}{ll}
                            0 &  \text{if} \ x\le  Q_0/2, \\
                           \frac{2x}{Q_0} -1 & \text{if} \ x\in
                                               (Q_0/2,Q_0], \\
                            1 &   \text{if} \ x >  Q_0.  \\
                          \end{array} \right.
\]
Observe that $\mathbbm{1}_{\{\overline{Y}(v) \geq Q_0\}}\le \chi(\overline{Y}(v))\le \mathbbm{1}_{\{\overline{Y}(v) \geq Q_0/2\}}$, and that $\chi$ is
Lipschitz with constant $2/Q_0$.
Therefore, if $\varepsilon_1,\ldots,\varepsilon_N$ are independent, symmetric $\{-1,1\}$-valued random variables that are independent of the $(Y_i)_{i=1}^N$, then
\begin{eqnarray*}
\lefteqn{
\mathbb{E} \sup_{v \in S^{d-1}} \frac{1}{N}\sum_{i=1}^N \mathbbm{1}_{\{\overline{Y}_i(v)
  \geq Q_0\}}      } \\
& \leq &
\mathbb{E} \sup_{v \in S^{d-1}} \frac{1}{N}\sum_{i=1}^N \chi(\overline{Y}_i(v)) \\
& \leq &
2\mathbb{E} \sup_{v \in S^{d-1}} \frac{1}{N}\left| \sum_{i=1}^N \varepsilon_i
         \chi(\overline{Y}_i(v)) \right|
+          \sup_{v \in S^{d-1}} \mathbb{E} \chi(\overline{Y}(v))  \\
& & \text{(by the Gin{\'e}-Zinn symmetrization theorem \cite{GiZi84})}
  \\
& \leq &
\frac{4}{Q_0} \mathbb{E} \sup_{v \in S^{d-1}} \frac{1}{N}\left| \sum_{i=1}^N \varepsilon_i
         \overline{Y}_i(v) \right|
+          \sup_{v \in S^{d-1}} \mathbb{E} \chi(\overline{Y}(v))
\\
& \stackrel{\mathrm{def.}}{=} & (*)~,
\end{eqnarray*}
where in the second step one uses the standard contraction lemma for
Rademacher averages, see Ledoux and Talagrand \cite{LeTa91}.

To bound the second term on the right-hand side, recall that $Q_0 \geq 16 \sqrt{\lambda_1/\varepsilon}$, and thus, for every $v \in S^{d-1}$,
\begin{eqnarray}
\label{eq:chebyshev}
\mathbb{E} \chi(\overline{Y}(v)) & \le & \mathbb{E} \mathbbm{1}_{\{\overline{Y}(v) \geq Q_0/2\}}= \mathbb{P}\left(
  \inr{\overline{X},v} \geq \frac{Q_0}{2}\right) \\
\nonumber
&  \leq & \frac{4 \mathbb{E}\inr{\overline{X},v}^2}{Q_0^2} \leq \frac{4 \lambda_1}{Q_0^2} \leq \frac{\varepsilon}{64}~.
\end{eqnarray}
To bound the first term, note that
\begin{equation*}
\mathbb{E} \sup_{v \in S^{d-1}} \left| \frac{1}{N}\sum_{i=1}^N \varepsilon_i \overline{Y}_i(v) \right| =  \mathbb{E} \sup_{v \in S^{d-1}} \left| \frac{1}{N}\sum_{i=1}^N \varepsilon_i \inr{X_i-\mu,v} \right|
\leq \sqrt{\frac{\mathrm{Tr}(\Sigma)}{N}}~.
\end{equation*}
Hence, by the definition of $Q_0$,
$$
(*) \leq \frac{\varepsilon}{32}~.
$$
By Talagrand's concentration inequality for empirical processes indexed by a class of uniformly bounded functions \cite{Tal96c}, with probability at least $1-\exp(-x)$,
$$
\frac{1}{N}\sup_{v \in S^{d-1}} \left|\left\{i : \overline{Y}_i(v) \geq
    Q_0\right\}\right| \leq
\frac{\varepsilon}{16}
+ \sqrt{\frac{x}{N}} \cdot \frac{\sqrt{\varepsilon}}{128} + \frac{10x}{N}
$$
(see  \cite[Exercise 12.15]{BoLuMa13} for the value of the numerical constant).

With the choice of $x = \varepsilon N/2560$ one has that, with probability at least $1-\exp(-\varepsilon N/2560)$,
$$
\sup_{v \in S^{d-1}} \left|\left\{i : \overline{Y}_i(v)\geq Q_0\right\}\right| \leq \frac{\varepsilon}{8} N~,
$$
as required.
{\mbox{}\nolinebreak\hfill\rule{2mm}{2mm}\par\medbreak}

Note that, when \eqref{eq:uniform-beta} holds, we have,
for every $v \in S^{d-1}$,
$$
\alpha_v-\inr{\mu,v} \geq  - Q_0  \ \ \ {\rm and} \ \ \ \beta_v - \inr{\mu,v} \leq Q_0~.
$$
Indeed, this follows from the fact that
for every $v \in S^{d-1}$ there are at most $(\varepsilon/8)N$ of the $\overline{Y}_i(v)$ that
are larger than $Q_0$. If, in addition, the adversary corrupts at most
$(\varepsilon/8) N$ of the points $Y_i$,
then there are still no more than $(\varepsilon/4) N$ values
$\inr{\widetilde{Y}_i,v}$
that are larger than $\inr{\mu,v}+Q_0$, which suffices for our purposes.
And, by the definition of $\varepsilon$, one has that $\varepsilon/8 \ge \eta$, as required.

Now consider some $Q$ that satisfies $2Q_0<Q \leq 4Q_0$, and
from here we condition on an event $E$ such that the inequalities  \eqref{eq:uniform-beta} both hold. By Lemma \ref{lemma:uniform-cutoff}, $E$ occurs with probability at least $1-\exp(-\varepsilon N/2560)$;
importantly, this event only depends on $Y_1,\ldots,Y_N$, the first half of the uncontaminated sample.

In particular, on the event $E$,  for every $v \in S^{d-1}$,
\[
 \beta_v -\inr{\mu,v} + Q \le Q_0 + Q \le 5Q_0
\]
and
\[
 \beta_v -\inr{\mu,v} + Q \ge  \alpha_v -\inr{\mu,v} + Q \ge - Q_0 + Q \ge Q_0~.
\]
By a similar argument one may obtain lower and upper bounds for $\alpha_v -\inr{\mu,v}$. Hence, on $E$, for every $v \in S^{d-1}$,
\begin{equation} \label{eq:up-low-alpha-beta}
-5Q_0 \leq \alpha_v-\inr{\mu,v}-Q \leq -Q_0, \ \ {\rm and} \ \ Q_0 \leq \beta_v-\inr{\mu,v}+Q \leq 5Q_0~.
\end{equation}

Finally, recall that
$$
U_Q(v)=\frac{1}{N} \sum_{i=1}^N \phi_{\alpha_v-Q,\beta_v+Q}\left(\inr{\widetilde{X}_i,v}\right)~,
$$
and in order to complete the proof of Proposition \ref{thm:main-vector}, it suffices to show
that $U_Q(v)$ is uniformly close to $\inr{\mu,v}$, with high probability.
In particular, the next lemma implies Proposition \ref{thm:main-vector}.

\begin{lemma} \label{thm:uniform-approx}
Let $2Q_0 \leq Q \leq 4Q_0$. Conditioned on the event $E$,
with probability at least $1-2\exp(-\varepsilon N/2560)$,
$$
\sup_{v \in S^{d-1}} \left| U_{Q}(v) - \inr{\mu,v} \right| \leq 2 \varepsilon Q~.
$$
\end{lemma}

\begin{proof}
We prove that
$$
\sup_{v \in S^{d-1}} \left( U_{Q}(v) - \inr{\mu,v} \right) \leq 2\varepsilon Q
$$
holds with the wanted probability; the proof that
$$
\sup_{v \in S^{d-1}} \left( \inr{\mu,v} - U_{Q}(v) \right) \leq 2\varepsilon Q
$$
follows an identical argument and is omitted.

As a first step, note that, in the expression of $U_Q(v)$, the
corrupted samples $\widetilde{X}_i$ may be harmlessly replaced by their
uncorrupted counterparts $X_i$. Indeed, by
 \eqref{eq:up-low-alpha-beta}, on the event $E$, the range of the function
$\phi_{\alpha_v-Q,\beta_v+Q}$
is an interval of length at most $10Q$ and therefore,
deterministically, for all $v\in
S^{d-1}$,
\[
  \frac{1}{N} \sum_{i=1}^N
  \phi_{\alpha_v-Q,\beta_v+Q}\left(\inr{\widetilde{X}_i,v}\right)
- \frac{1}{N} \sum_{i=1}^N
\phi_{\alpha_v-Q,\beta_v+Q}\left(\inr{X_i,v}\right)
\le \eta \cdot 10Q \le \varepsilon Q~.
\]
Once again, recalling that on $E$ \eqref{eq:up-low-alpha-beta}
holds, it follows that
\[
\frac{1}{N} \sum_{i=1}^N
\phi_{\alpha_v-Q,\beta_v+Q}\left(\inr{X_i,v}\right)
\le \frac{1}{N} \sum_{i=1}^N
\phi_{\inr{\mu,v}-Q_0, \inr{\mu,v}+5Q_0}\left(\inr{X_i,v}\right)~.
\]
Since the event $E$ only depends on the uncorrupted sample
$Y_1,\ldots,Y_N$, the right-hand side of the above inequality is
independent of $E$.
Thus, writing
\[
\overline{U}_Q(v) = \frac{1}{N} \sum_{i=1}^N \phi_{\inr{\mu,v}-Q_0,
  \inr{\mu,v}+5Q_0}(\inr{X_i,v})-\inr{\mu,v}
= \frac{1}{N} \sum_{i=1}^N \phi_{-Q_0, 5Q_0}(\inr{X_i-\mu,v})~,
\]
it suffices to prove that, with probability at least
$1-2e^{-\varepsilon N/2560}$,
$$
\sup_{v \in S^{d-1}} \overline{U}_Q(v) \leq \varepsilon Q~.
$$
To that end, consider the decomposition
\[
\sup_{v \in S^{d-1}} \overline{U}_Q(v)
\leq  \sup_{v \in S^{d-1}} \left( \overline{U}_Q(v)- \mathbb{E} \overline{U}_Q(v) \right)+   \sup_{v \in S^{d-1}} \mathbb{E} \overline{U}_Q(v) \stackrel{\mathrm{def.}}{=} (1) + (2)~.
\]
First, let us bound the term $(1)$ in several steps.

Set
$$
\overline{W}_Q(v) = \frac{1}{N}\sum_{i=1}^N \phi_{-3Q,3Q}(\inr{X_i-\mu,v})~,
$$
and note that
\begin{eqnarray*}
\sup_{v \in S^{d-1}} \left( \overline{U}_Q(v)- \mathbb{E} \overline{U}_Q(v) \right)
& \le & \sup_{v \in S^{d-1}} \left( \overline{U}_Q(v)- \overline{W}_Q(v) \right) \\
& & + \sup_{v \in S^{d-1}} \left( \overline{W}_Q(v)- \mathbb{E} \overline{W}_Q(v) \right) \\
& & + \sup_{v \in S^{d-1}} \left( \mathbb{E} \overline{W}_Q(v)- \mathbb{E} \overline{U}_Q(v)
    \right) \\
& \stackrel{\mathrm{def.}}{=} & (a) + (b) + (c)~.
\end{eqnarray*}
To bound term $(a)$, recall that $2Q_0 \le Q \le  4Q_0$, implying that
$\phi_{-Q_0,5Q_0}(x) \not = \phi_{-3Q,3Q}(x)$ only if
\[
\text{either} \quad
 x < -Q_0, \quad \text{or} \quad x > 5Q_0~.
\]
In both cases
$$
\left|\phi_{-Q_0,5Q_0}(x) - \phi_{-3Q,3Q}(x)\right| \leq 3Q~.
$$
By Lemma \ref{lemma:uniform-cutoff}, with probability at least $1-\exp(-\varepsilon N/2560)$,
$$
\sup_{v \in S^{d-1}} \left|\{i : \inr{X_i-\mu,v} > 5Q_0 \ \ {\rm or} \ \  \inr{X_i-\mu,v} < -Q_0\}\right| \leq \frac{\varepsilon N}{4}~,
$$
hence, on this event,
$$
(a) \leq \frac{3\varepsilon Q}{4}~.
$$
One may control term $(c)$ similarly. For each $v\in S^{d-1}$,
\[
\mathbb{E} \overline{W}_Q(v)- \mathbb{E} \overline{U}_Q(v) \le 3Q \cdot \mathbb{P}\{|\inr{X-\mu,v}|>
Q_0\} \le \frac{3\varepsilon Q}{64}
\]
by recalling \eqref{eq:chebyshev}.

The term $(b)$ is controlled using Talagrand's concentration inequality for the
supremum of empirical processes. Note that for every $v \in S^{d-1}$,
$$
\left|\phi_{-3Q,3Q}\left(\inr{\overline{X},v}\right)\right| \leq 3Q \quad \text{and}
\quad \mathbb{E} \left| \phi_{-3Q,3Q}\left(\inr{\overline{X},v}\right)\right|^2 \leq  \mathbb{E}
\left|\inr{\overline{X},v}\right|^2  \leq \lambda_1~.
$$
Also, since $\phi_{-3Q,3Q}(x)$ is a $1$-Lipschitz function that passes
through $0$, by a contraction argument (see Ledoux and Talagrand \cite{LeTa91}),
$$
\mathbb{E} \sup_{v \in S^{d-1}} \left|\overline{W}_Q(v) - \mathbb{E} \overline{W}_Q(v)\right| \leq 2\mathbb{E} \sup_{v \in S^{d-1}} \left|\frac{1}{N}\sum_{i=1}^N \varepsilon_i \inr{X_i-\mu,v} \right| \leq 2 \sqrt{\frac{\mathrm{Tr}(\Sigma)}{N}}~.
$$
Hence, by Talagrand's inequality, with probability at least $1-2\exp(-x)$,
$$
\sup_{v \in S^{d-1}} \left|\overline{W}_Q(v) - \mathbb{E} \overline{W}_Q(v)\right|
\leq 4 \sqrt{\frac{\mathrm{Tr}(\Sigma)}{N}}+ 2\sqrt{\lambda_1} \sqrt{\frac{x}{N}} + 20Q\frac{x}{N} \leq \frac{\varepsilon Q}{64}
$$
with the choice of $x = \varepsilon N/2560$, recalling the definition of
$Q_0$, and using that $Q \ge 2Q_0$. This concludes the proof that $(1) \leq (1/2+1/32+1/400)\varepsilon Q$ with probability $1-e^{-\varepsilon N/2560}$.

Finally, it remains to estimate term $(2)$:
$$
(2)=\sup_{v \in S^{d-1}} \mathbb{E} \overline{U}_Q(v) = \sup_{v \in S^{d-1}}\mathbb{E} \phi_{-Q_0, 5Q_0} \left(\inr{\overline{X},v}\right)~.
$$
Clearly $X_v=\inr{\overline{X},v}$ is centered and
$\phi_{-Q_0, 5Q_0} (X_v) \not = X_v$ only when either $X_v \geq 5Q_0$ or $X_v \leq -Q_0$. Hence,
\begin{eqnarray*}
 \mathbb{E} \phi_{-Q_0, 5Q_0} (X_v)
& = &
 \mathbb{E} \left(\phi_{-Q_0, 5Q_0} (X_v) - X_v\right) \\
& \le & \mathbb{E} |Q_0+X_v| \mathbbm{1}_{X_v \le -Q_0}
\\
& \leq & \frac{\varepsilon Q}{64}
\end{eqnarray*}
by an argument analogous to \eqref{eq:ebound} and using \eqref{eq:chebyshev}.
\end{proof}

With Proposition \ref{thm:main-vector} proved, let us complete
the proof of Theorem \ref{thm:main}.
Let $i_0$ be such that $Q \stackrel{\mathrm{def.}}{=} 2^{i_0} \in [2Q_0,4Q_0)$ and let $E$ be the ``good'' event
that both \eqref{eq:uniform-beta} and
$$
\sup_{v \in S^{d-1}} \left| U_{Q}(v) - \inr{\mu,v} \right| \leq 2 \varepsilon Q
$$
hold. Recall that
$$
U_Q(v)=\frac{1}{N} \sum_{i=1}^N \phi_{\alpha_v-Q,\beta_v+Q}\left(\inr{\widetilde{X}_i,v}\right)~;
$$
$E$ holds with probability at least $1-\delta$; and on $E$,
any point in $\Gamma(2^{i_0})$ is within distance $4\varepsilon Q_0$ of the mean
$\mu$.
Hence, it suffices to show that on the event $E$, the sets $\Gamma(2^i)$ for $i \geq
i_0$ are nested. Indeed, by the definition of $i^*$,
$$
\emptyset \neq \bigcap_{i \geq i^*} \Gamma(2^i) \subset \Gamma(2^{i_0}),
$$
and thus $\|\widehat{\mu}-\mu\| \leq 4\varepsilon Q_0$.

To see that $\Gamma(2^{i_0})\subset \Gamma(2^{i_0+1})$  it is enough
to show that, for all $v \in S^{d-1}$,  $|\inr{x,v}-U_{2Q}(v)| \leq 4\varepsilon Q$.
But if $x \in \Gamma(v,Q)$ for some $v\in S^{d-1}$, it follows that
$$
|\inr{x,v}-U_{2Q}(v)|  \leq  |\inr{x,v}-U_Q(v)|+|U_Q(v)-U_{2Q}(v)| \leq 2\varepsilon Q + |U_Q(v)-U_{2Q}(v)|;
$$
therefore, it suffices to show that $|U_Q(v)-U_{2Q}(v)| \leq 2 \varepsilon Q$.

Note that on the event $E$, there are at most $\varepsilon N/4$ sample points
$\widetilde{X}_i$ such that $\inr{\widetilde{X}_i,v}$ is above or below the levels $\alpha_v-2^{i_0}$ and
$\beta_v+2^{i_0}$.
Hence, the number of points for which $U_Q(v) \not = U_{2Q}(v)$ is at
most $\varepsilon N/4$ and so the difference is at most $(2Q \varepsilon N/4)/N
= \varepsilon Q/2$.

By induction, the same argument shows that, on the event $E$,
$\Gamma(2^i) \subset \Gamma(2^{i+1})$ for every $i \geq i_0$,
completing the proof of Theorem \ref{thm:main}.

\subsection*{Acknowledgements}
We thank the referees and the associate editor for  insightful
comments and pointing out relevant connections to
previous work.