text:
\section{Introduction}
\label{sec:intro}

Let $(S,\mathcal S)$ be the measurable space, and $X\in S$ be a random variable with distribution $P$.
Moreover, suppose that $X_1,\ldots,X_N$ are i.i.d. copies of $X$.
Assume that $\mathcal F$ is a class of measurable functions from $S$ to $\mathbb R$.
Many problems in mathematical statistics and statistical learning theory require simultaneously estimating $Pf:=\mathbb Ef(X)$ for all $f\in \mathcal F$. For example, in the maximum likelihood estimation framework, $\mathcal F=\left\{ \log p_\theta(\cdot), \ \theta\in \Theta \right\}$ is a family of probability density functions with respect to a $\sigma$-finite measure $\mu$, and $\frac{dP}{d\mu}=p_{\theta_\ast}$ for $\theta_\ast \in\Theta$.
The most common way to estimate $\mathbb Ef(X)$ is via the empirical mean $P_N f:=\frac{1}{N}\sum_{j=1}^N f(X_j)$.
Deviations of the resulting \emph{empirical process} $\mathcal F\ni f\mapsto \sqrt{N}(P_N - P)f$ have been extensively studied, however, sharp estimates are known only under rather restrictive conditions, such as the case when functions in $\mathcal F$ are uniformly bounded, or when the envelope $F(x) := \sup_{f\in \mathcal F}|f(x)|$ of the class $\mathcal F$ possesses finite exponential moments \cite{wellner1,kolt6,bartlett2005local,geer2000empirical,Adamczak:2008aa}.

Here, we consider the situation when the random variables $\{f(X), \ f\in \mathcal F\}$ indexed by $\mathcal F$ are allowed to be heavy-tailed, meaning that they possess finite moments of low order only (in the context of this paper, ``low order'' will usually mean the range between $2$ and $3$).
In this case, the tail probabilities $P\left( \left|\frac{1}{N}\sum_{j=1}^N f(X_j) - \mathbb Ef(X) \right| \geq t \right)$ decay polynomially, making many existing techniques unapplicable.
Our approach to simultaneous mean estimation is based on replacing the sample mean by a different estimator of $\mathbb Ef(X)$ that is ``robust'' to heavy tails and admits tight concentration under minimal moment assumptions.
Well known examples of such estimators include the median-of-means (MOM) estimator \cite{Nemirovski1983Problem-complex00,alon1996space,lerasle2011robust} and Catoni's estimator \cite{catoni2012challenging}.
These two techniques rely on different principles for controlling the bias: while Catoni's estimator is (informally speaking) based on delicate ``truncation,'' the MOM estimator exploits the fact that both the median and the mean of a symmetric distribution coincide with the center of symmetry \cite{minsker2017distributed}.
Construction proposed in this work shows that these principles can be unified. We suggest a family of estimators that can be viewed as a ``bridge'' between Catoni's estimator and the MOM technique, and prove uniform bounds for the deviations of the resulting stochastic process.
We also address the more challenging framework of adversarial contamination and show that estimators of the mean of a random vector obtained using our methods admit optimal performance bounds in this case.

\subsection{Notation and organization of the paper.}
\label{sec:definitions}

Absolute positive constants will be denoted $c,C,c_1$, etc., and may take different values in different parts of the paper.
For a function $h:\mathbb R\mapsto\mathbb R$, define
\[
\argmin_{z\in\mathbb R} h(z) := \{z\in\mathbb R: h(z)\leq h(x)\text{ for all }x\in \mathbb R\},
\]
and $\|h\|_\infty:=\mathrm{ess \,sup}\{ |h(x)|: \, x\in \mathbb R\}$. For a Lipschitz continuous function $h$, $L(h)$ will denote its Lipschitz constant.
For $f\in \mathcal F$, denote $\sigma^2(f) = \mbox{Var}(f(X))$ and $\sigma^2(\mathcal F) = \sup_{f\in \mathcal F}\sigma^2(f)$.
Everywhere below, $\Phi(\cdot)$ stands for the cumulative distribution function of the standard normal random variable, and $W(f)$ denotes a random variable with distribution $N\left( 0,\sigma^2(f) \right)$. Additional notation and auxiliary results are introduced as necessary.

Material of the paper is organized as follows: section \ref{sec:construction} explains the main ideas behind construction of the estimators studied in the paper. The main results are  stated in section \ref{sec:M-est}, followed by discussion and comparison to the literature on the topic in section \ref{sec:comparison}.
Section \ref{sec:adversary} discuss extensions of the results in the framework of adversarial contamination.
Finally, section \ref{section:mean} explores implications of the bounds for the problem of multivariate mean estimation.
Finally, the proofs are presented in section \ref{sec:proofs}.

\section{Construction of robust estimators of the mean.}
\label{sec:construction}

Proposed estimators are based on the following (informally stated) principles:
\begin{enumerate}[(a)]
\item  If the distribution $Q$ is symmetric, then its center of symmetry $\theta(Q)$ can be approximated by a robust estimator, such as Huber's robust M-estimator of location \cite{huber1964robust} defined via
\begin{center}
$\widehat\theta := \argmin\limits_{z\in \mathbb R} \sum_{j=1}^N \rho\left( z - Y_j\right)$,
\end{center}
where $Y_1,\ldots,Y_N$ is an i.i.d. sample from $Q$ and $\rho$ is a convex, even function with bounded derivative.
\item In order to construct a robust estimator of a parameter $\theta^\diamond(Q)$ of (not necessarily symmetric) distribution $Q$ based on an i.i.d. sample $Y_1,\ldots,Y_N$, create an auxillary sample $\xi_1,\ldots,\xi_M$ such that
\begin{enumerate}
\item[(i)] it is governed by an approximately symmetric distribution;
\item[(ii)] the center of symmetry of this distribution is close to $\tilde\theta(P)$.
\end{enumerate}
According to (a), we then define an estimator of $\theta^\diamond(Q)$ via
\[
\widehat \theta^\diamond := \argmin\limits_{z\in \mathbb R} \sum_{j=1}^M \rho\left( z - \xi_j\right).
\]

\end{enumerate}

The main focus of this work is the case when $Q$ is the distribution of $f(X)$ and $\theta^\diamond(Q)$ corresponds to the mean $\mathbb E f(X)$.
To construct a ``new sample'' $\xi_1,\ldots,\xi_M$ governed by an approximately symmetric distribution centered at $\mathbb Ef(X)$, we rely on the fact that, under mild assumptions, the sample mean is asymptotically normal, hence asymptotically symmetric.
Let $k$ be an integer, and assume that $G_1,\ldots,G_k$ are subsets of the index set $\{1,\ldots,N\}$ of cardinality $|G_j| = n:= \lfloor N/k\rfloor$ each, where the partition method is independent of the data $X_1,\ldots,X_N$. In general, we do not require the subsets to be disjoint, and different possibilities will be discussed in the following sections.
Let
\[
\bar \theta_j(f) = \frac{1}{n}\sum_{i\in G_j} f(X_i)
\]
be the empirical mean evaluated over the subsample indexed by $G_j$.
Conditions on the suitable ``loss function'' $\rho$ are summarized in the following assumption.
\begin{assumption}
\label{ass:1}
Suppose that $\rho: \mathbb R\mapsto \mathbb R$ is a convex, even, continuously differentiable function such that
\begin{enumerate}
\item[(i)] $\rho'(z)=z$ for $|z|\leq 1$ and $\rho'(z)=\mathrm{const}$ for $z\geq 2$.
\item[(ii)] $z - \rho'(z)$ is nondecreasing;
\end{enumerate}
\end{assumption}
\noindent For instance, Huber's loss \cite{huber1964robust}
\begin{equation*}
\rho(z)=\frac{z^2}{2} I\{|z|\leq 1\} + \left( |z| - 1/2\right) I\{|z|>1\}
\end{equation*}
is an example of a function satisfying Assumption \ref{ass:1}.
\begin{remark}
\label{rem:sup}
Assumption \ref{ass:1} implies that $\rho'(2) - 2\leq \rho'(1)-1 = 0$, hence $\|\rho'\|_\infty \leq 2$. Moreover, for any $x>y$,
$\rho'(x) - \rho'(y) = y - \rho'(y) - (x - \rho'(x)) + x - y \leq x-y$, hence $\rho'$ is Lipschitz continuous with Lipschitz constant $L(\rho')=1$.
\end{remark}
Note that the loss $\rho(x)=|x|$ that leads to a ``classical'' median-of-means estimator does not satisfy assumption \ref{ass:1}, in particular, $\rho'$ is not Lipschitz continuous. Lipschitz continuity of $\rho'$ turns out to be crucial for the derivation of our uniform bounds, however, for finite classes $\mathcal F$, the proofs are valid for broader class of losses that includes $\rho(x)=|x|$; see \cite{minsker2017distributed} for more details.
The principles and assumptions stated above lead to the following definition of robust mean estimators: given $\Delta > 0$, set
\begin{align}
\label{eq:M-est}
\widehat\theta^{(k)}(f):= \argmin_{z\in \mathbb R}\frac{1}{\sqrt{N}}\sum_{j=1}^k \rho\left(\sqrt{n}\,\frac{\bar \theta_j(f) - z}{\Delta}\right).
\end{align}
Parameter $\Delta$, when expressed on a ``natural scale'' of the problem defined by $\sigma(\mathcal F)$, can be interpreted as the truncation level. It will be shown that different combinations of the subgroup size $n$ and ``truncation level'' $\Delta$ may lead to equally good bounds: in particular, when $n=1$ and $\Delta\propto \sigma(\mathcal F)\sqrt{N}$, we will recover Catoni's estimator, while the case of large $n$ (e.g., $n\simeq \sqrt{N}$) and $\Delta\propto \sigma(\mathcal F)$ leads to the MOM-type estimator.

	\begin{comment}

\begin{remark}
Estimator \eqref{eq:M-est} has been previously analyzed in \cite{minsker2017distributed} under weaker requirements on the function $\rho$, namely, imposing only condition (i) of Assumption \ref{ass:1}. In particular, such weaker conditions are satisfied by the ``classical'' median-of-means estimator corresponding to $\rho(x)=|x|$.
However, inequalities obtained in \cite{minsker2017distributed} are non-uniform, meaning that they only provide an upper bound for $\sup_{f\in \mathcal F}\,P\left(\left| \widehat\theta^{(k)}(f) - Pf \right| \geq t\right)$. The problem considered here is more general and difficult which justifies additional, however still rather mild, assumptions on $\rho$.
Choice of $\rho$ also affects the asymptotic behavior of the estimator \eqref{eq:M-est}: for fixed $f$, the central limit theorem for $\widehat\theta^{(k)}(f)$ (Theorem 3 in \cite{minsker2017distributed}) explains how the asymptotic variance of $\widehat\theta^{(k)}(f)$ depends on $\rho$. In particular, the asymptotic variance is smaller when Huber's loss \eqref{eq:huber-loss} is used instead of the absolute value loss $\rho(x)=|x|$, as one would expect.
\end{remark}

	\end{comment}

\subsection{Main results.}
\label{sec:M-est}

The collection of random variables $\left\{ \widehat\theta^{(k)}(f) - Pf,  \ f\in \mathcal F\right\}$ defines a stochastic process that is a natural analogue of the empirical process in the framework of heavy-tailed data.
Our main goal is to characterize the size of the supremum of the process, namely
\footnote{We assume everywhere below that $\sup_{f\in \mathcal F} \left| \widehat\theta^{(k)}(f) - Pf \right|$ is properly measurable. See \cite{wellner1,dudley2014uniform} for in-depth discussion of measurability issues.}
\[
\sup_{f\in \mathcal F} \left| \widehat\theta^{(k)}(f) - Pf \right|.
\]
In particular, we will be interested in estimating the deviation probabilities $P\left( \sup_{f\in \mathcal F} \left| \widehat\theta^{(k)}(f) - Pf \right| \geq t\right)$ under minimal assumptions on the process $\left\{ f(X), \ f\in \mathcal F\right\}$.
As a corollary of our general bounds, we will obtain new results for the problem of mean estimation in $\mathbb R^d$.
Everywhere below, it will be assumed that $\sigma(\mathcal F)<\infty$.

As a first step, we introduce the main quantities appearing in our bounds.
Given $f\in \mathcal F$ such that $\sigma(f)>0$, $n\in \mathbb N$ and $t>0$, define
\begin{multline*}
g_f(t,n):= C \Bigg( \frac{ \mathbb E (f(X) - \mathbb Ef(X))^2 \, I\left\{ \frac{ |f(X)-\mathbb Ef(X)|}{\sigma(f)\sqrt{n}} >  1+\left|\frac{t}{\sigma(f)}\right| \right\} }{\sigma^2(f) \left(1+\left|\frac{t}{\sigma(f)}\right| \right)^2}
\\
+ \frac{1}{\sqrt{n}}
\frac{\mathbb E |f(X)-\mathbb Ef(X)|^3 \, I\left\{ \frac{|f(X) - \mathbb Ef(X)|}{\sigma(f)\sqrt{n}} \leq 1+ \left|\frac{t}{\sigma(f)}\right|\right\}}{\sigma^3(f) \left(1+\left|\frac{t}{\sigma(f)}\right| \right)^3}\Bigg).
\end{multline*}
It follows from the results of L. Chen and Q.-M. Shao \cite[Theorem 2.2 in][]{chen2001non} that $g_f(t,n)$ controls the rate of convergence in the central limit theorem, namely
\begin{equation}
\label{eq:BE-main}
\left| \pr{ \frac{\sum_{j=1}^n \left(f(X_j) - Pf\right)}{\sigma(f)\sqrt{n}} \leq t} - \Phi( t ) \right| \leq g_f(t,n),
\end{equation}
given that $\sigma^2(f)<\infty$ and that an absolute constant $C$ in the definition of $g_f(t,n)$ is large enough.
The function $g_f(t,n)$ enters our bounds through the quantity that we define next. Given $\Delta>0$, set
\[
G_f(n,\Delta) := \int_{0}^{\infty} g_f\left(\Delta\left( \frac{1}{2} + t \right),n \right)dt.
\]
The following statement provides simple upper bounds for $g_f(t,n)$ and $G_f(n,\Delta)$.
\begin{lemma}
\label{lemma:BE-nonunif}
Let $X_1,\ldots,X_n$ be i.i.d. copies of $X$, and assume that $\mbox{Var}(f(X))<\infty.$ Then $g_f(t,n)\to 0$ as $|t|\to\infty$ and $g_f(t,n)\to 0$ as $n\to\infty$, with convergence being monotone. Moreover, if $\mathbb E| f(X) - \mathbb Ef(X)|^{2+\delta}<\infty$ for some $\delta\in (0,1]$, then for all $t>0$
\begin{align}
\label{eq:g_f}
g_f(t,n)&\leq C'  \frac{\mathbb E\big|f(X) - \mathbb Ef(X) \big|^{2+\delta}}{n^{\delta/2}\left(\sigma(f)+ \left| t \right| \right)^{2+\delta}} \leq C' \frac{\mathbb E\big|f(X) - \mathbb Ef(X)\big|^{2+\delta}}{n^{\delta/2} |t|^{2+\delta}},
\\
\nonumber
G_f(n,\Delta) & \leq C'' \frac{\mathbb E\big|f(X) - \mathbb Ef(X)\big|^{2+\delta}}{\Delta^{2+\delta} n^{\delta/2}},
\end{align}
where $C',C''>0$ are absolute constants.
\end{lemma}
\noindent The proof of this lemma is outlined in section \ref{proof:BE-nonunif}.
We are now ready to state the main result.
Let $\rho$ be a loss function satisfying Assumption \ref{ass:1}.
Moreover, set
\[
\widetilde \Delta:=\max\left( \Delta,\sigma(\mathcal F)\right).
\]
\begin{theorem}
\label{th:unif}
Assume that $N=nk$ and that the subgroups $G_1,\ldots,G_k$ are disjoint.
Then there exist absolute constants $c,\, C>0$ such that for all $s>0,$ $n$ and $k$ satisfying
\begin{equation}
\label{eq:assump}
\frac{1}{\Delta} \left( \frac{1}{\sqrt{k}} \, \mathbb E\sup_{f\in \mathcal F} \frac{1}{\sqrt{N}}\sum_{j=1}^N \left( f(X_j) - Pf \right) + \sigma(\mathcal F)\sqrt{\frac{s}{k}} \right) +
\sup_{f\in\mathcal F} G_f(n,\Delta)
+ \frac{s}{k} \leq c,
\end{equation}
the following inequality holds with probability at least $1 - 2e^{-s}$:
\begin{multline*}
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \frac{\widetilde \Delta}{\Delta} \left( \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \sqrt{\frac{s}{N}} \right)
\\
+ \widetilde \Delta \left( \sqrt{n}\frac{s}{N}
+ \frac{\sup_{f\in\mathcal F} G_f(n,\Delta)}{\sqrt{n}} \right) \Bigg].
\end{multline*}
\end{theorem}
\noindent The proof of the theorem is outlined in section \ref{proof:unif}.
We note that the requirement $N=nk$ is not restrictive, as replacing $N$ by $k\cdot \lfloor N/k \rfloor$ will only result in the change of absolute constants.
The assumption that the groups sizes are equal is also not essential and is only imposed to avoid overly technical and cumbersome expressions.
When the class $\mathcal F$ is P-Donsker \cite{dudley2014uniform},
$\limsup\limits_{N\to\infty} \Big| \mathbb E\sup\limits_{f\in \mathcal F} \frac{1}{\sqrt N} \sum_{j=1}^N \left( f(X_j) - Pf \right) \Big|$ is bounded, hence condition \eqref{eq:assump} holds for $N$ large enough whenever $s$ is not too big and $\Delta$ is not too small, namely, $s\leq c'k$ and $\Delta \geq c'' \sigma(\mathcal F)$. When discussing examples in the following section, this will be our default setup.

Estimator $\widehat\theta^{(k)}(f)$ defined in \eqref{eq:M-est} depends on the choice of subgroups $G_1,\ldots,G_k$. It is natural to ask if there exists a version of $\widehat \theta^{(k)}(f)$ that is permutation-invariant. We address this question below and present a construction based on U-statistics.
For an integer $n\leq \frac{N}{2}$, let $k=\lfloor N/n\rfloor$, and define
\[
\mathcal A_N^{(n)}:=\left\{  J: \ J\subseteq \{1,\ldots,N\}, \mathrm{Card}(J)=n \right\}.
\]
Let $h$ be a measurable function of $n$ variables. Recall that a U-statistic of order $n$ with kernel $h$ based on the i.i.d. sample $X_1,\ldots,X_N$ is defined as \citep{hoeffding1948class}
\begin{equation}
\label{u-stat}
U_{N,n} = \frac{1}{{N\choose n}}\sum_{J\in \mathcal A_N^{(n)}} h \left( \{X_j\}_{j \in J} \right).
\end{equation}
Given $J\in A_N^{(n)}$, let $\bar\theta(f; J):=\frac{1}{n}\sum_{i\in J} f(X_i)$. Consider U-statistics of the form
\[
U_{N,n}(z;f) = \frac{1}{{N\choose n}} \sum_{J\in \mathcal A_N^{(n)}} \rho\left(\sqrt{n}\,\frac{\bar \theta(f;J) - z}{\Delta}\right),
\]
and set
\begin{equation*}
\widetilde\theta^{(k)}(f):= \argmin_{z\in \mathbb R} U_{N,n}(z;f).
\end{equation*}
\begin{theorem}
\label{th:unif-U}
There exist absolute constants $c,\, C>0$ such that for all $s>0,$ $n$ and $k$ satisfying
\begin{equation}
\label{eq:assump}
\frac{1}{\Delta} \left( \frac{1}{\sqrt{k}} \, \mathbb E\sup_{f\in \mathcal F} \frac{1}{\sqrt{N}}\sum_{j=1}^N \left( f(X_j) - Pf \right) + \sigma(\mathcal F)\sqrt{\frac{s}{k}} \right) +
\sup_{f\in\mathcal F} G_f(n,\Delta)
+ \frac{s}{k} \leq c,
\end{equation}
the following inequality holds with probability at least $1 - 2e^{-s}$:
\begin{multline*}
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \frac{\widetilde \Delta}{\Delta} \left( \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \sqrt{\frac{s}{N}} \right)
\\
+ \widetilde \Delta \left( \sqrt{n}\frac{s}{N}
+ \frac{\sup_{f\in\mathcal F} G_f(n,\Delta)}{\sqrt{n}} \right) \Bigg].
\end{multline*}

	\begin{comment}
Assume that $k$ and $s>0$ are such that
\[
\frac{8 L(\rho')}{\Delta \sqrt{k}} \, \mathbb E\sup_{f\in \mathcal F} \left|\frac{1}{\sqrt{nk}} \sum_{j=1}^{nk} \left( f(X_j) - Pf \right)\right| +
\|\rho'\|_\infty \sqrt{\frac{2s}{k}}+ 2\|\rho'\|_\infty \sup_{f\in \mathcal F} g(f;n) \leq \frac{1}{2\, K(\rho)}.
\]
Then the following inequality holds with probability at least $1 - 2e^{-s}$:
\begin{multline*}
\sup_{f\in \mathcal F}\left| \widetilde \theta^{(k)}(f) - Pf \right| \leq
K(\rho)
\Bigg( \frac{8 L(\rho')}{\sqrt{nk}} \max\left(1, \frac{\sigma(\mathcal F)}{\Delta} \right)\, \mathbb E\sup_{f\in \mathcal F} \left|\frac{1}{\sqrt{nk}} \sum_{j=1}^{nk} \left( f(X_j) - Pf \right)\right|
\\
+ \max\left(\Delta,\sigma(\mathcal F)\right) \left\|\rho' \right\|_\infty \left( \sqrt{\frac{2 s}{nk}}
+ 2 \sup_{f\in \mathcal F} \frac{g(f;n)}{\sqrt{n}}  \right) \Bigg).
\end{multline*}
	\end{comment}
\end{theorem}
The resulting deviation bounds for $\widetilde \theta^{(k)}(f)$ are of exactly the same form as for the estimator $\widehat\theta^{(f)}(f)$ that is based on disjoint blocks of data. The proof of this result is given in section \ref{proof:unif-U}.

\subsection{Discussion and comparison with existing bounds.}
\label{sec:comparison}

A number of recent works address the problem of robust empirical risk minimization that is closely related to the question addressed in the present paper.
In \cite{brownlees2015empirical}, authors prove uniform deviation bounds for robust mean estimators defined using O. Catoni's approach \cite{catoni2012challenging}; these bounds are limited by their dependence on the covering numbers of the class $\mathcal F$ with respect to the sup-norm $\left\| \cdot \right\|_\infty$.
  Uniform bounds for the median-of-means estimators have been obtained in several papers, including \cite{lugosi2016risk,lecue2018robust,lugosi2017regularization,lecue2017robust}.
Result that is closest to our setting has been obtained in \cite{lecue2018robust}: proof of Theorem 2 of that paper implies that the estimator $\widehat\theta^{(k)}_{\mathrm{med}}(f)$ corresponding to $\rho(x)=|x|$ satisfies
\begin{equation}
\label{eq:slow}
\sup_{f\in \mathcal F}\left| \widehat\theta^{(k)}_{\mathrm{med}}(f) - Pf \right| \leq
C
\Bigg( \frac{1}{\sqrt{N}} \, \mathbb E\sup_{f\in \mathcal F} \left| \frac{1}{\sqrt{N}} \sum_{j=1}^N \left( f(X_j) - Pf \right)\right|
+ \sigma(\mathcal F) \sqrt{\frac{k}{N}} \Bigg)
\end{equation}
with probability at least $1 - e^{-ck}$ for absolute constant $c,C>0$; a slightly stronger version of this result has appeared in \cite{lugosi2018near}.
The key difference between this inequality and the bound of Theorem \ref{th:unif} is the fact that the former holds only for the fixed value of the confidence parameter $s=k$, while the latter typically provides deviation guarantees over the wide range  $0<s\leq ck$ of confidence parameter $s$.
This difference is important, as one usually wants to choose $k$ as large as possible to improve robustness (in particular, robustness to adversarial contamination) without degrading performance of the estimator.
The price that we have to pay is the necessity to tune the parameter $\Delta$. However, as we show below, in many cases there is a wide range of ``suitable'' choices of $\Delta$, so this issue is not critical.

Let us consider two examples.
First, assume that $n=1$, $k=N$ and set $\Delta = \Delta(s):= \sigma(\mathcal F)\sqrt{\frac{N}{s}}$. In this case, for $N$ large enough, condition \eqref{eq:assump} reduces to $s\leq c' N$, and we deduce from Theorem \ref{th:unif} that
\[
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \sqrt{\frac{s}{N}} \Bigg]
\]
with probability at least $1-2e^{-s}$.
This inequality recovers, up to constants, the result of Catoni \cite{catoni2012challenging} for $\mathcal F=\{ f\}$ (indeed, in this case the expected supremum is $0$), and improves upon uniform bounds obtained for Catoni-type estimators in \cite{brownlees2015empirical}. If $\Delta = \sigma(\mathcal F)\sqrt{N}$, we get the ``sub-exponential'' bound
\[
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \frac{1+s}{\sqrt{N}} \Bigg]
\]
that holds with probability at least $1-e^{-s}$ uniformly for $s\leq c' N$.
Moreover, if
\[
\kappa_{2+\delta}(\mathcal F):=\frac{\sup_{f\in \mathcal F} \mathbb E|f(X) - \mathbb Ef(X)|^{2+\delta}}{\sigma^{2+\delta}(\mathcal F)}<\infty
\]
for some $\delta\in(0,1]$, then the estimator is less sensitive to the choice of the parameter $\Delta$. Specifically,
\begin{equation}
\label{eq:corollary}
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \sqrt{\frac{s}{N}} \Bigg]
\end{equation}
with probability at least $1-2e^{-s}$ for any $\Delta$ satisfying
$\sigma(\mathcal F)\left( \frac{N}{s}\right)^{\frac{1}{2(1+\delta)}} \left(\kappa_{2+\delta}(\mathcal F)\right)^{1/(1+\delta)} \leq \Delta \leq \sigma(\mathcal F)\sqrt{\frac{N}{s}}$. For instance, if $\delta=1$, then any $\Delta$ in the range $\sigma(\mathcal F)(N/s)^{1/4}\lesssim \Delta \lesssim \sigma(\mathcal F)\sqrt{N/s}$ is suitable.
Equivalently, for a given $\Delta$, the sub-Gaussian type bound \eqref{eq:corollary} holds uniformly for all $s \in \left[ \kappa^2_{3} \frac{M_\Delta^{4}}{N}, M_\Delta^2\right]$ where $M_\Delta = \frac{\sigma(\mathcal F)\sqrt{N}}{\Delta}$.

\noindent Next, assume that $N\gg n\geq 2$. For $\Delta = \sigma(\mathcal F)\sqrt{\frac k s}$, we again recover the bound
\[
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \sqrt{\frac{s}{N}} \Bigg]
\]
that holds with probability at least $1-2e^{-s}$.
When $\Delta\asymp \sigma(\mathcal F)$, $\widehat \theta^{(k)}(f)$ most closely resembles the median-of-means estimator.
In this case, the inequality that holds with probability at least $1-2e^{-s}$ is
\[
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \left(\sqrt{\frac{s}{N}} + \sqrt{\frac k N}\sup_{f\in \mathcal F} G_f(n,\sigma(\mathcal F)) \right) \Bigg].
\]
As $\sup_{f\in \mathcal F} G_f(n,\sigma(\mathcal F))$ is small for large $n$, this bound is clearly better than \eqref{eq:slow}.
Finally, let us again consider the case when stronger moment assumptions hold, namely, $\kappa_3(\mathcal F)<\infty$.
Combining the estimate for $\sup_{f\in \mathcal F}G_f(n,\Delta)$ provided by Lemma \ref{lemma:BE-nonunif} and the bound of Theorem \ref{th:unif}, we obtain that
\begin{multline*}
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \sqrt{\frac{s}{N}}
\\
+ \frac{\sup_{f\in \mathcal F}\mathbb E|f(X) - \mathbb Ef(X)|^3}{\Delta^2} \frac{k}{N} + \Delta \frac{s}{\sqrt{kN}}\Bigg],
\end{multline*}
again with probability at least $1-2e^{-s}$.
If $\Delta$ is such that $c_1\sigma(\mathcal F)\left(1\vee\sqrt{\frac{k}{\sqrt{Ns}}} \right) \leq \Delta \leq c_2\sigma(\mathcal F)\sqrt{k/s}$ then this inequality implies sub-Gaussian deviation bounds at confidence level $s$.
If for instance $1\ll k\ll \sqrt{N}$ and $\Delta \asymp \sigma(\mathcal F)$, then
\[
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \sqrt{\frac{s}{N}} \Bigg]
\]
for all $s\leq c'k$ uniformly.

	\begin{comment}

For any $\Delta:=\Delta(k)$ such that $\sigma(\mathcal F)\ll \Delta \ll \sigma(\mathcal F)\sqrt{k}$, Theorem \ref{th:unif} implies that
\begin{equation*}
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+\sigma(\mathcal F) \left( \sqrt{\frac{s}{N}} + o(1)\frac{s+\sqrt{k}}{\sqrt{N}}\right) \Bigg]
\end{equation*}
that holds with probability at least $1 - 2e^{-s}$ whenever $s\leq c'k$. Here, $o(1)$ stands for $\max\left( \frac{\sigma(\mathcal F)}{\Delta(k)}, \frac{\Delta(k)}{\sigma(\mathcal F)\sqrt{k}}\right)$ that goes to $0$ as $k,n\to\infty$.

For example, consider the plausible situation when $\kappa_3:=\sup_{f\in \mathcal F} \frac{\mathbb E|f(X) - \mathbb Ef(X)|^3}{\sigma^3(f)}<\infty$, whence $\sup_{f\in \mathcal F} g(f;n) \leq \frac{0.4748 \, \kappa_3}{\sqrt{n}}$.
Taking $k=c_1\lfloor \sqrt{N}\rfloor$ and assuming that $c_2 \sigma(\mathcal F)\leq \Delta\leq c_3\sigma(\mathcal F)$ for some $c_1,c_2,c_3 > 0$, we see that Theorem \ref{th:unif} implies the inequality
\[
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C(\rho)
\Bigg( \frac{1}{\sqrt{N}} \, \mathbb E\sup_{f\in \mathcal F} \left| \frac{1}{\sqrt{N}} \sum_{j=1}^N \left( f(X_j) - Pf \right)\right| + \sigma(\mathcal F)  \left( \sqrt{\frac{s}{N}}
+\kappa_3\frac{1}{\sqrt{N}} \right) \Bigg)
\]
that holds with probability at least $1 - 2e^{-s}$ for all $s\leq c_3 \sqrt{N}$ and $k$ large enough,
while \eqref{eq:slow} only states that for the same choice of $k$,
\[
\sup_{f\in \mathcal F}\left| \widehat\theta^{(k)}_{\mathrm{med}}(f) - Pf \right| \leq
C
\Bigg( \frac{1}{\sqrt{N}} \, \mathbb E\sup_{f\in \mathcal F} \left| \frac{1}{\sqrt{N}} \sum_{j=1}^N \left( f(X_j) - Pf \right)\right|
+ \sigma(\mathcal F)N^{-1/4} \Bigg)
\]
with probability at least $1-e^{-c_5\sqrt{N}}$.

Another remark that highlights the difference between Theorem \ref{th:unif} and bound \eqref{eq:slow} is related to the size of the expectation $\mathbb E \left| \widehat\theta^{(k)}(f) - Pf \right|$ for fixed $f\in \mathcal F$.
In this case, it follows from the standard bound for the median-of-means estimator (for example, Proposition 1 in \cite{lerasle2011robust} or Theorem 4.1 in \cite{devroye2016sub}) that for all $s>1$,
\begin{equation}
\label{eq:infinity}
\left| \widehat\theta^{(k)}_{\mathrm{med}}(f) - Pf \right| \leq C \sigma(f) \sqrt{\frac{k}{N}}\, s
\end{equation}
with probability at least $1 - s^{-k}$, implying that
\begin{equation}
\label{eq:mom1}
\mathbb E\left| \widehat\theta^{(k)}_{\mathrm{med}}(f) - Pf \right|\leq C_1 \sigma(f) \sqrt{\frac{k}{N}}.
\end{equation}
On the other hand, equations \eqref{eq:one-sided} applied to $\mathcal F=\left\{ f\right\}$ imply that
\begin{equation}
\label{eq:strong}
\left| \widehat\theta^{(k)}(f) - Pf \right| \leq C(\rho') \, \max\left(\Delta,\sigma(f)\right) \left( \sqrt{\frac{s}{N}} + g(f;n)\sqrt{\frac{k}{N}} \right)
\end{equation}
with probability $\geq 1 - 2e^{-s}$ whenever $s\leq c_4 k$ and $g(f;n) \leq c_5$.
This bound can be combined with a version of the inequality \eqref{eq:infinity} that holds for the estimator \eqref{eq:M-est} with $\rho(\cdot)$ being the Huber's loss to deduce that for $k\leq \frac{C_3}{g^2(f;n)}$, estimator $\widehat\theta^{(k)}$ satisfies the bound $\mathbb E \left| \widehat\theta^{(k)}(f) - Pf \right| \leq C_4 \frac{\max\left(\Delta,\sigma(f)\right)}{\sqrt{N}}$ which is stronger than \eqref{eq:mom1} whenever $\Delta\leq c \,\sigma(f)$. Details of the computation are outlined in Appendix \ref{section:expectation}.

It is important to stress the fact that performance of the estimators $\left\{\widehat\theta^{(k)}(f), \ f\in \mathcal F \right\}$ depends on the choice of parameter $\Delta$, with the ``optimal'' value being, according to Theorem \ref{th:unif}, of order $\sigma(\mathcal F)$ that is usually unknown; it is possible to ``adapt'' to the unknown $\sigma(\mathcal F)$ via Lepski's method, as discussed in the following section.
At the same time, in the special case $\rho(x)=|x|$, the resulting estimator $\widehat\theta^{(k)}_{\mathrm{med}}(f)$ does not require any tuning. We leave an interesting question concerning validity of the bounds of Theorem \ref{th:unif-mom} for general classes $\mathcal F$ for future study.

		\end{comment}

\section{Contamination with outliers.}
\label{sec:adversary}

Assume that the initial dataset of cardinality $N$ is merged with a set of $\mathcal O<N$ outliers that are generated by an adversary who has an opportunity to inspect the data, and the combined dataset of cardinality $N^\circ = N+\mathcal O$ is presented to a statistician.
We would like to understand performance of proposed estimators $\widehat \theta^{(k)}(f)$ in this more challenging framework.
Let $G_1,\ldots,G_k$ be the disjoint partition of the index set $\{1,\ldots,N^\circ\}$ that the estimators $\left\{\widehat \theta^{(k)}(f), \ f\in \mathcal F\right\}$ are based on; as before, $n$ will stand for the cardinality of $G_j$.

In the rest of the section, we will assume that $k>2\mathcal O$.
Let $J\subset \{1,\ldots,k\}$ of cardinality $|J|\geq k-\mathcal O$ be the subset containing all $j$ such that the subsample $\{ X_i, \ j\in G_j\}$ does not include outliers. Clearly, $\{ X_i: \ i\in G_j, \ j\in J\}$ are still i.i.d. as the partitioning scheme is independent of the data.
Moreover, set $N_J:=\sum_{j\in J} |G_j|$, and note that
\[
N_J\geq n |J|\geq \frac{kn}{2}.
\]
The following analogue of Theorem \ref{th:unif} holds.
\begin{theorem}
\label{th:unif2}
There exist absolute constants $c,\, C>0$ such that for all $s>0,$ $n$ and $k$ satisfying
\begin{equation}
\label{eq:assump}
\frac{1}{\Delta} \left( \frac{1}{\sqrt{k}} \, \mathbb E\sup_{f\in \mathcal F} \frac{1}{\sqrt{N}}\sum_{j=1}^N \left( f(X_j) - Pf \right) + \sigma(\mathcal F)\sqrt{\frac{s}{k}} \right) +
\sup_{f\in\mathcal F} G_f(n,\Delta)
+ \frac{s+\mathcal O}{k} \leq c,
\end{equation}
the following inequality holds with probability at least $1 - 2e^{-s}$:
\begin{multline*}
\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right| \leq
C
\Bigg[ \frac{\widetilde \Delta}{\Delta} \left( \mathbb E\sup_{f\in \mathcal F} \frac{1}{N} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \sigma(\mathcal F) \sqrt{\frac{s}{N}} \right)
\\
+ \widetilde \Delta \left( \sqrt{n}\frac{s+ \mathcal O}{N}
+ \frac{\sup_{f\in\mathcal F} G_f(n,\Delta)}{\sqrt{n}} \right) \Bigg].
\end{multline*}
\end{theorem}
It is convenient to interpret the inequality as follows: if $\mathcal O\leq c k$ for a sufficiently small absolute constant $c$, the error $\sup_{f\in \mathcal F}\left| \widehat \theta^{(k)}(f) - Pf \right|$ behaves like the maximum of 2 terms: the first term is the error bound for the case $\mathcal O = 0$, and the second term is of order
$\widetilde\Delta \sqrt{n}\frac{\mathcal O}{N}$. In the next section, we provide examples which show that the dependence on $\mathcal O$ in our bounds is, in general, non-improvable.

\subsection{Estimators of the mean of a random vector.}
\label{section:mean}

Assume that $X_1,\ldots,X_N$ are i.i.d. copies of a random vector $X\in \mathbb R^d$ with mean $\mathbb EX = \mu$ and covariance matrix $\mathbb E(X-\mu)(X-\mu)^T = \Sigma$.
Let $\|\cdot\|$ be some norm in $\mathbb R^d$, and let $B$ be the unit ball with respect to this norm, $B=\left\{ x\in \mathbb R^d: \ \|x\|\leq 1\right\}$. Consider the class of linear functionals $\mathcal F=\left\{ f_v(x)=\langle v,x \rangle, \ v\in B\right\}$.
Our goal is to estimate the mean $\mu$, with the error measured in the norm $\|\cdot\|$.
Construction that we propose is closely related to the approach employed previously by several authors \cite{joly2017estimation,lugosi2018near,catoni2016pac,giulini2018robust} that is based on combining estimators of one-dimensional projections.
Assume that we are in the ``adversarial contamination'' framework of Theorem \ref{th:unif2}.
Let $\rho$ be a function satisfying assumption \ref{ass:1}, and let $\widehat\theta^{(k)}(v)$ be the estimator of $\langle \mu,v \rangle$, the projection of $\mu$ in direction $v\in B$:
\[
\widehat\theta^{(k)}(v):= \argmin_{z\in \mathbb R}\frac{1}{\sqrt{N}}\sum_{j=1}^k \rho\left(\sqrt{n}\,\frac{\bar \mu_j(v) - z}{\Delta}\right),
\]
where $\bar\mu_j(v)=\frac{1}{n}\sum_{i\in G_j}\langle v,X_j\rangle$, and $\Delta\geq \sqrt{\lambda_{\max}(\Sigma)}$.
Given $v\in B$ and $\varepsilon>0$, define the closed ``slab''
\[
S_v(\varepsilon):=\left\{ y\in \mathbb R^d: \ \left| \langle y, v \rangle - \widehat\theta^{(k)}(v) \right| \leq \varepsilon\right\},
\]
and $M(\varepsilon):=\bigcap_{v\in B} S_v(\varepsilon)$.
Finally, let $\varepsilon_\ast:=\inf\left\{ \varepsilon>0: \ M(\varepsilon)\ne \emptyset\right\}$, and
take $\widehat\mu^{(k)}$ to be any element in $M(\varepsilon_\ast)$ (indeed, $M(\varepsilon_\ast) = \bigcap_{\varepsilon > \varepsilon_\ast} M(\varepsilon)$ is non-empty as an intersection of nested compact sets).
\begin{corollary}
\label{cor:norm}
There exist absolute constants $\tilde c,\tilde C>0$ with the following properties: assume that
\begin{equation}
\label{cond:2}
\max\left( \frac{1}{\sqrt{k}\Delta}  \, \mathbb E\sup_{v\in B} \left| \frac{1}{\sqrt{N}}  \sum_{j=1}^N \langle v, X_j - \mu \rangle \right| + \frac{s}{k} + \sup_{v\in B} G_f(n,\Delta), \frac{\mathcal O}{k}   \right) \leq \tilde c.
\end{equation}
Then with probability at least $1-2e^{-s}$,
\[
\left\| \widehat\mu^{(k)} - \mu\right\| \leq \tilde C \Bigg(  \mathbb E\sup_{v\in B}  \frac{1}{N} \sum_{j=1}^N \langle v, X_j - \mu \rangle +
\sqrt{\lambda_{\max}(\Sigma)}\sqrt{\frac{s}{N}} + \Delta\left( \sup_{v\in B}  \frac{G_{f_v}(n,\Delta)}{\sqrt n} + \sqrt{n}\frac{s+\mathcal O}{N}\right)
 \Bigg).
\]
\end{corollary}
\begin{proof}
It follows from Theorem \ref{th:unif2} that on the event $\mathcal E$ of probability at least $1-2e^{-s}$, $\mu\in M(\varepsilon)$ for all
\[
\varepsilon\geq \varepsilon_0:=C \Bigg( \mathbb E\sup_{f\in \mathcal F}  \frac{1}{N}  \sum_{j=1}^N \langle v, X_j - \mu \rangle +
\sqrt{\lambda_{\max}(\Sigma)}\sqrt{\frac{s}{N}} + \Delta\left( \sup_{v\in B}  \frac{G_{f_v}(n,\Delta)}{\sqrt n} + \sqrt{n}\frac{s+\mathcal O}{N}\right)
 \Bigg)
\]
given that \eqref{cond:2} holds, hence $\varepsilon_\ast \leq \varepsilon_0$ on event $\mathcal E$. Consequently,
\[
\left\| \widehat\mu^{(k)} - \mu \right\| = \sup_{v\in B}\left| \langle \widehat\mu^{(k)} - \mu,v\rangle \right|
\leq \sup_{v\in B}\left| \langle \widehat\mu^{(k)} ,v\rangle - \widehat\theta^{(k)}(v) \right| + \sup_{v\in B}\left| \langle \mu ,v\rangle -  \widehat\theta^{(k)}(v)\right| \leq \varepsilon_\ast + \varepsilon_0 \leq 2\varepsilon_0
\]
with probability at least $1 - 2e^{-s}$.
\end{proof}

In the special case when $\|\cdot\|$ is the Euclidean norm $\|\cdot\|_2$, the bound of Corollary \ref{cor:norm} can be further simplified. It follows from H\"{o}lder's inequality that
\begin{multline*}
\mathbb E\sup_{v\in \mathbb R^d: \|v\|_2=1} \left| \frac{1}{\sqrt{N}}  \sum_{j=1}^N \langle v, X_j - \mu \rangle \right|
\leq \mathbb E^{1/2}\sup_{v\in \mathbb R^d: \|v\|_2=1} \left| \frac{1}{\sqrt{N}}  \sum_{j=1}^N \langle v, X_j - \mu \rangle \right|^2
\\
= \sqrt{\frac{1}{N} \mathbb E \left\| \sum_{j=1}^N (X_j - \mu)\right\|_2^2} = \sqrt{\mathbb E \left\| X - \mu \right\|_2^2} =\sqrt{\mbox{tr\,} \Sigma},
\end{multline*}
hence $\widehat \mu^{(k)}$ satisfies
\[
\left\| \widehat\mu^{(k)} - \mu\right\|_2 \leq C \Bigg( \sqrt{\frac{\mbox{tr\,} \Sigma}{N}} + \sqrt{\lambda_{\max}(\Sigma)}\sqrt{\frac{s}{N}} + \Delta\left( \sup_{v\in B}  \frac{G_{f_v}(n,\Delta)}{\sqrt n} + \sqrt{n}\frac{s+\mathcal O}{N}\right) \Bigg)
\]
with probability at least $1 - 2e^{-s}$ (whenever $s\leq c'k$).
According to the discussion in section \ref{sec:comparison}, in many cases the term
$\Delta\left( \sup_{v\in B}  \frac{G_{f_v}(n,\Delta)}{\sqrt n} + \sqrt{n}\frac{s+\mathcal O}{N} \right)$ is of order smaller than $N^{-1/2}$, whence the estimator $\widehat\mu^{(k)}$ behaves like the sample mean of the Gaussian random variables \cite{lugosi2018near}.

Let us now discuss optimality with respect to adversarial contamination. Assume that $\mathcal O = \varepsilon N$ for $\varepsilon\geq \frac{1}{N}$; here, we assume $\varepsilon$  to be known in advance, and the issue of adaptivity is beyond the scope of this paper.
 Moreover, suppose that
\[
\kappa_{2+\delta}:=\sup_{v: \|v\|_2=1}\frac{\mathbb E \left| \langle v,X - \mu\rangle \right|^{2+\delta}}{\left( \mbox{Var}\langle v,X-\mu\rangle\right)^{1+\delta/2}} < \infty
\]
for some $\delta\in(0,1]$. In this case, Lemma \ref{lemma:BE-nonunif} implies that
\[
\sup_{v\in B} G_{f_v}(n,\Delta)\leq C \frac{\sup_{\|v\|_2=1} \mathbb E\left| \dotp{X-\mu}{v}\right|^{2+\delta}}{\Delta^{2+\delta}n^{\delta/2}}
\]
for some absolute constant $C>0$.
Let $M_\Delta:=\frac{\Delta}{\sigma(\mathcal F)}$, and recall that $M_\Delta\geq 1$ by assumption. Then, choosing
$k = \varepsilon^{\frac{2}{2+\delta}}\, N\frac{M_\Delta^2 }{\kappa^{\frac{2}{2+\delta}}_{2+\delta}}$, we deduce from Corollary \ref{cor:norm} that
\[
\left\| \widehat\mu^{(k)} - \mu\right\|_2 \leq C \Bigg( \sqrt{\frac{\mbox{tr\,} \Sigma}{N}} + \sqrt{\lambda_{\max}(\Sigma)}\left(\sqrt{\frac{s}{N}} + \varepsilon^{\frac{1+\delta}{2+\delta}}\, \kappa^{1/(2+\delta)}_{2+\delta} \right) + \frac{\kappa^{1/(2+\delta)}_{2+\delta}}{\varepsilon^{1/(2+\delta)} N}\, s \Bigg)
\]
with probability at least $1-2e^{-s}$. Since $\varepsilon\geq \frac{1}{N}$, $\varepsilon^{1/(2+\delta)} N \geq N^{-\frac{1+\delta}{2+\delta}} = o\left( N^{-1/2} \right)$ whenever $\delta>0$, hence the last term in the bound is of smaller order.
According to Lemma \ref{lemma:minmax} (see section \ref{section:supplement}), no estimator can achieve rate faster than $\varepsilon^{\frac{1+\delta}{2+\delta}}$ with respect to $\varepsilon$, implying that our estimator is optimal in this sense.

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

We will introduce some additional notation and recall useful results that we rely upon in the proofs.
Denote
\[
G_k(z;f) = \frac{1}{\sqrt{k}}\sum_{j=1}^k \rho'\left( \sqrt{n}\,\frac{ (\bar \theta_j(f) - Pf) - z}{\Delta} \right)
\]
and let $\widehat \theta_0^{(k)}(f)$ be any solution of the equation $G_k\left(\widehat \theta_0^{(k)}(f);f\right)=0$.
Clearly, $\widehat \theta_0^{(k)}(f) = \widehat \theta^{(k)}(f) - Pf$ is the error of the estimator $\widehat \theta^{(k)}(f)$.

\noindent The following concentration inequality is due to Klein and Rio (see section 12.5 in \cite{boucheron2013concentration}).
\begin{fact}
\label{fact:ineq}
Let $\{Z_j(f), \ f\in \mathcal F\}, \ j=1,\ldots,N$ be independent (not necessarily identically distributed) separable stochastic processes indexed by class $\mathcal F$ and such that $|Z_j(f)-\mathbb EZ_j(f)|\leq M$ a.s. for all $1\leq j\leq N$ and $f\in \mathcal F$. Then the following inequality holds with probability at least $1-e^{-s}$:
\begin{align}
\label{eq:klein1}
\sup_{f\in \mathcal F}\left( \sum_{j=1}^N (Z_j(f) - \mathbb EZ_j(f)) \right) &\leq 2\mathbb E\sup_{f\in \mathcal F} \left( \sum_{j=1}^N (Z_j(f) - \mathbb EZ_j(f))\right)
+V(\mathcal F)\sqrt{2s}+\frac{4Ms}{3},
\end{align}
where $V^2(\mathcal F)=\sup_{f\in \mathcal F}\sum_{j=1}^N \mbox{Var}\left( Z_j(f)\right)$.
\end{fact}
\noindent It is easy to see, applying \eqref{eq:klein1} to processes $\{-Z_j(f), \ f\in \mathcal F\}$, that
\begin{equation}
\label{eq:klein2}
\inf_{f\in \mathcal F}\left( \sum_{j=1}^N (Z_j(f) - \mathbb EZ_j(f))\right) \geq -2\mathbb E\sup_{f\in \mathcal F} \left( \sum_{j=1}^N (\mathbb EZ_j(f) - Z_j(f))\right)
 - V(\mathcal F)\sqrt{2s} - \frac{4Ms}{3}
\end{equation}
with probability at least $1-e^{-s}$.
Moreover, \eqref{eq:klein1} is a corollary of the following bound for the moment generating function:
\begin{equation}
\label{eq:mgf}
\log \mathbb E e^{\lambda \left( \sum_{j=1}^N (Z_j(f) - \mathbb EZ_j(f))\right)}\leq \frac{e^{\lambda M} - \lambda M - 1}{M^2}\left( V^2(\mathcal F) + 2M \,\mathbb E\sup_{f\in \mathcal F} \left( \sum_{j=1}^N (Z_j(f) - \mathbb E Z_j(f))\right)\right)
\end{equation}
that holds for all $\lambda>0$.
This fact provides a straightforward extension of the concentration bounds to the case of U-statistics.
Let $\pi_N$ be the collection of all permutations $i:\{1,\ldots,N\}\mapsto \{1,\ldots,N\}$.
Given $(i_1,\ldots,i_N)\in \pi_N$ and a U-statistic $U_{N,n}$ defined in \eqref{u-stat}, let
\begin{equation*}
T_{i_1,\ldots,i_N}:=\frac{1}{k}\left( h\left(X_{i_1},\ldots,X_{i_n} \right) + h\left(X_{i_{n+1}},\ldots,X_{i_{2n}}\right) + \ldots +
h\left(X_{i_{(k-1)n+1}},\ldots,X_{i_{kn}} \right) \right).
\end{equation*}
It is well known (see section 5 in \cite{hoeffding1963probability}) that the following representation holds:
\begin{equation}
\label{eq:U-decomp}
U_{N,n} = \frac{1}{N!}\sum_{(i_1,\ldots,i_N) \in \pi_N}  T_{i_1,\ldots,i_N}.
\end{equation}
Let $U_{N,n}'(z;f) = \frac{1}{{N\choose n}} \sum_{J\in \mathcal A_N^{(n)}} \rho'\left(\sqrt{n}\,\frac{(\bar \theta(f;J) - Pf) - z}{\Delta}\right)$.
Applied to $U'_{N,n}(z;f)$, relation \eqref{eq:U-decomp} yields that
\[
U'_{N,n}(z;f) = \frac{1}{N!}\sum_{(i_1,\ldots,i_N)\in \pi_N} T_{i_1,\ldots,i_N}(z;f),
\]
where
\begin{multline*}
T_{i_1,\ldots,i_N}(z;f) = \frac{1}{k}\Big(  \rho'\left(\sqrt{n}\,\frac{\bar \theta(f;\{i_1,\ldots,i_n\}) - Pf - z}{\Delta}\right) +
\\
\ldots +  \rho'\left(\sqrt{n}\,\frac{\bar \theta(f;\{i_{(k-1)n+1},\ldots,i_{kn}\}) - Pf - z}{\Delta}\right) \Big).
\end{multline*}
Jensen's inequality implies that for any $\lambda>0$,
\begin{multline*}
\mathbb E \exp\left( \frac{\lambda}{N!} \sum_{(i_1,\ldots,i_N)\in \pi_N} \left( T_{i_1,\ldots,i_N}(z;f) -\mathbb E T_{i_1,\ldots,i_N}(z;f)\right)\right)
\\
\leq \frac{1}{N!} \sum_{(i_1,\ldots,i_N)\in \pi_N} \mathbb E \exp\Big( \lambda \left( T_{1,\ldots,N}(z;f) -\mathbb E T_{1,\ldots,N}(z;f)\right) \Big),
\end{multline*}
hence bound \eqref{eq:mgf} can be applied and yields that
\begin{multline}
\label{eq:U-concentr}
\sup_{f\in \mathcal F}\left( U'_{N,n}(z;f) - \mathbb U'_{N,n}(z;f)\right) \leq 2\mathbb E\sup_{f\in \mathcal F}\left( T_{1,\ldots,N}(z;f) - \mathbb E T_{1,\ldots,N}(z;f) \right)
\\
+ \sup_{f\in \mathcal F}\sqrt{\mbox{Var}\left( \rho'\left(\sqrt{n}\,\frac{\bar \theta(f;\{1,\ldots,n\}) - Pf - z}{\Delta}\right)\right)}\sqrt{\frac{2s}{k}} + \frac{8s\|\rho'\|_\infty}{3k}
\end{multline}
with probability at least $1-e^{-s}$. The expression can be further simplified by noticing that $\|\rho'\|_\infty\leq 2$ and that
\[
\mbox{Var}\left( \rho'\left(\sqrt{n}\,\frac{\bar \theta(f;\{1,\ldots,n\}) - Pf - z}{\Delta}\right)\right) \leq \frac{\sigma^2(f)}{\Delta^2}.
\]
due to Lemma \ref{lemma:variance}.

\subsection{Proof of Theorem \ref{th:unif}.}
\label{proof:unif}

Recall that
\[
G_k(z;f) = \frac{1}{\sqrt{k}}\sum_{j=1}^k \rho'\left( \sqrt{n}\,\frac{ (\bar \theta_j(f) - Pf) - z}{\Delta} \right).
\]
Suppose $z_1,z_2$ are such that on an event of probability close to $1$, $G_k(z_1;f) > 0$ and $G_k(z_2;f) < 0$ for all $f\in \mathcal F$ simultaneously.
Since $G_k$ is decreasing in $z$, it is easy to see that $\widehat \theta_0^{(k)}(f)\in (z_1,z_2)$ for all $f\in \mathcal F$ on this event, implying that $\left| \sup_{f\in \mathcal F}\widehat \theta_0^{(k)}(f) \right|\leq \max(|z_1|,|z_2|)$.
Hence, our goal is to find $z_1,z_2$ satisfying conditions above and such that $|z_1|,\, |z_2|$ are as small as possible.
We will provide detailed bounds for $z_1$, while the steps to estimate $z_2$ are quite similar.
Observe that
\begin{multline*}
G_k(z;f) = \frac{1}{\sqrt{k}} \sum_{j=1}^k \left(  \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) - \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)  \right)  \\
+ \frac{1}{\sqrt{k}}\sum_{j=1}^k  \left( \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) -
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \right) +
\frac{1}{\sqrt{k}}\sum_{j=1}^k \mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right).
\end{multline*}
We will proceed in 3 steps: first, we will find $\varepsilon_1>0$ such that for any $z\in \mathbb R$,
\begin{equation}
\label{eq:eps1}
\inf_{f\in \mathcal F} \frac{1}{\sqrt{k}}\sum_{j=1}^k \left( \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) - \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)  \right) \geq -\varepsilon_1
\end{equation}
with high probability, then $\varepsilon_2>0$ such that
\begin{equation*}
\inf_{f\in \mathcal F} \frac{1}{\sqrt{k}}\sum_{j=1}^k\left( \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) -
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \right) \geq -\varepsilon_2,
\end{equation*}
and finally we will choose $z_1<0$ such that for all $f\in \mathcal F$,
\begin{equation}
\label{eq:z1}
\frac{1}{\sqrt{k}} \sum_{j=1}^k \mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z_1 }{\Delta} \right) > \varepsilon_1 + \varepsilon_2.
\end{equation}
It follows from Lemma \ref{lemma:step1} that setting
\[
\varepsilon_1 =  \frac{8 }{\Delta\sqrt{N}} \, \mathbb E\sup_{f\in \mathcal F} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \frac{\sigma(\mathcal F)}{\Delta}\sqrt{2s} + \frac{16}{3}\frac{s}{\sqrt{k}}
\]
guarantees that \eqref{eq:eps1} holds with probability at least $1 - e^{-s}$.
Next, Lemma \ref{lemma:step2} implies that $\varepsilon_2$ can be chosen as
\[
\varepsilon_2 = 2\sqrt{k}\,\sup_{f\in\mathcal F} G_f(n,\Delta).
\]
Finally, we apply Lemma \ref{lemma:step3} with
\[
\varepsilon := \frac{\varepsilon_1 + \varepsilon_2}{\sqrt{k}}
\]
to deduce that
\begin{equation*}
z_1 = -  \frac{1}{0.09}
 \bigg( \frac{8 L(\rho')}{N}\frac{\widetilde \Delta}{\Delta} \, \mathbb E\sup_{f\in \mathcal F}  \sum_{j=1}^N \left( f(X_j) - Pf \right)\ + \sigma(\mathcal F)\frac{\widetilde \Delta}{\Delta}\sqrt{\frac{2s}{N}} + \widetilde \Delta\frac{16}{3} \frac{s\sqrt{n}}{N} + 2\frac{\sup_{f\in \mathcal F} G_f(n,\Delta)}{\sqrt{n}} \Bigg)
\end{equation*}
satisfies \eqref{eq:z1} under assumption that $\varepsilon\leq 0.045$.
Proceeding in a similar way, it is easy to see that setting $z_2=-z_1$ guarantees that $G_k(z_2;f)<0$ for all $f\in \mathcal F$ with probability at least $1 - e^{-s}$, hence the claim follows.

\begin{lemma}
\label{lemma:step1}
For any $z\in \mathbb R$ and $\rho$ satisfying Assumption \ref{ass:1}, the inequalities
\begin{align*}
\inf_{f\in \mathcal F}\frac{1}{\sqrt{k}} \sum_{j=1}^k &\left(  \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) - \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)  \right)  \\
&\geq -\frac{8}{\Delta\sqrt{N}} \, \mathbb E\sup_{f\in \mathcal F} \sum_{j=1}^N \left( f(X_j) - Pf \right)
- \frac{\sigma(\mathcal F)}{\Delta}\sqrt{2s} - \frac{16}{3} \frac{s}{\sqrt{k}},
\\
\sup_{f\in \mathcal F}\frac{1}{\sqrt{k}} \sum_{j=1}^k &\left(  \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) - \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)  \right)  \\
&\leq \frac{8}{\Delta\sqrt{N}} \, \mathbb E\sup_{f\in \mathcal F} \sum_{j=1}^N \left( f(X_j) - Pf \right)
+ \frac{\sigma(\mathcal F)}{\Delta}\sqrt{2s} + \frac{16}{3}\frac{s}{\sqrt{k}},
\end{align*}
hold with probability at least $1-e^{-s}$ each.
\end{lemma}
\begin{proof}
We will prove the first inequality, while the second follows similarly.
First observe that in view of Lemma \ref{lemma:variance},
\[
\mbox{Var}\left( \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) \right) \leq \mbox{Var}\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)
= \frac{\sigma^2(f)}{\Delta^2},
\]
hence $\sup_{f\in \mathcal F} \mbox{Var}^{1/2}\left( \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) \right) \leq \frac{\sigma(\mathcal F)}{\Delta}$. Next, Fact \ref{fact:ineq} (more specifically, inequality \eqref{eq:klein2}) implies that for any fixed $z\in \mathbb R$,
\begin{multline*}
\inf_{f\in \mathcal F} \sum_{j=1}^k \frac{1}{\sqrt{k}} \left( \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) - \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)  \right) \\
\geq
-2\mathbb E\sup_{f\in \mathcal F}\frac{1}{\sqrt{k}} \sum_{j=1}^k  \left( \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) -  \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) \right)
\\
- \frac{\sigma(\mathcal F)}{\Delta}\sqrt{2s} - 8\left\|\rho' \right\|_\infty \frac{s}{3\sqrt{k}}
\end{multline*}
with probability at least $1 - e^{-s}$.
It follows from Remark \ref{rem:sup} that $\|\rho'\|_\infty \leq 2$, hence it remains to estimate the expected supremum.
To this end, we will apply symmetrization and Talagrand's contraction inequalities
\footnote{We use the versions of these inequalities without absolute values inside the supremem; see \cite{medina2014learning} for the proof.}
\cite{kolt6,LT-book-1991,medina2014learning} (where functions
$h_j(x) := -\frac{\rho'\left(x - \sqrt{n}z/\Delta\right) - \rho'\left( - \sqrt{n}z/\Delta\right)}{L(\rho')}$ are contractions satisfying $h_j(0)=0$).
Let $\varepsilon_1,\ldots,\varepsilon_k$ be i.i.d. Rademacher random variables independent of $X_1,\ldots,X_N$, and note that
\begin{multline*}
\mathbb E\sup_{f\in \mathcal F}\frac{1}{\sqrt{k}} \sum_{j=1}^k \left(  -\rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) + \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)  \right)  \\
\leq 2 L(\rho') \, \mathbb E\sup_{f\in \mathcal F}\frac{1}{\sqrt{k}} \sum_{j=1}^k \varepsilon_j  h_j\left( \sqrt{n}\frac{\bar \theta_j(f) - Pf}{\Delta} \right)
\leq \frac{4 }{\Delta} \, \mathbb E\sup_{f\in \mathcal F} \sum_{j=1}^k \varepsilon_j \frac{\sqrt{n}}{\sqrt{k}} (\bar\theta_j(f) - Pf),
\end{multline*}
where we used the fact that $L(\rho')\leq 1$. Next, desymmetrization inequality \cite{kolt6} implies that
\[
\mathbb E\sup_{f\in \mathcal F} \sum_{j=1}^k \varepsilon_j \frac{\sqrt{n}}{\sqrt{k}} (\bar\theta_j(f) - Pf) \leq
\frac{2}{\sqrt{N}} \mathbb E\sup_{f\in \mathcal F} \sum_{j=1}^N \left( f(X_j) - Pf \right).
\]
and the result follows.
\end{proof}

\begin{lemma}
\label{lemma:step2}
Assume that $\mathbb E|f(X) - \mathbb Ef(X)|^{2}<\infty$ for all $f\in \mathcal F$ and that $\rho$ satisfies Assumption \ref{ass:1}. Then for all $f\in \mathcal F$ and $z\in \mathbb R$ satisfying $|z|\leq \frac{1}{2}\frac{\Delta}{\sqrt{n}}$,
\[
\left|\mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) -
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \right|  \leq
2 \,G_f(n,\Delta).
\]
	\begin{comment}

Moreover, if $\mathbb E|f(X) - \mathbb Ef(X)|^{2+\delta}<\infty$ for some $\delta\in[0,1]$, then there exists an absolute constant $C>0$ such that
\[
\left|\mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) -
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \right| \leq
C \,\frac{\mathbb E|f(X) - \mathbb Ef(X)|^{2+\delta}}{\Delta^{2+\delta}} \frac{1}{M^{1+\delta} \, n^{\delta/2}}.
\]

	\end{comment}
\end{lemma}
\begin{proof}
Let $T(x) = x - \rho'(x)$, and note that $T(x)=0$ for $|x| \leq 1$ by Assumption \ref{ass:1}. Moreover, $T$ is non-decreasing. As
\[
\mathbb E\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} - \frac{W(f) - \sqrt{n} z }{\Delta}\right)=0,
\]
it is easy to check that
\begin{multline*}
\left|\mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) -
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \right|
\\
= \left| \mathbb E \left( T\left( \sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta}\right) - T\left(  \frac{W(f) - \sqrt{n} z }{\Delta}  \right) \right) \right|.
\end{multline*}
For any bounded non-negative function $h:\mathbb R\mapsto \mathbb R_+$ and any signed measure $Q$,
\begin{align*}
\left| \int_{\mathbb R} h(x)dQ \right| = \left| \int_{0}^{\infty} Q\left( x: \,h(x)\geq t \right) dt \right|.
\end{align*}
Since any bounded function $h:\mathbb R\mapsto \mathbb R$ can be written as $h = h_+ - h_-$, where  $h_+=\max(h,0)$ and $h_- = \max(-h, 0)$ are both nonnegative, we deduce that
\begin{equation}
\label{eq:c1}
\left| \int_{\mathbb R} h(x)dQ \right|\leq  \int_{0}^{\infty} |Q\left( x: \,h_+(x)\geq t \right)| dt +  \int_{0}^{\infty} |Q\left( x: \,h_-(x)\geq t \right)| dt.
\end{equation}
Moreover, if $h$ is monotone, the sets $\{x: \,h_+(x)\geq t\}$ and $\{x: \,h_-(x)\geq t\}$ are half-intervals.
Take $h=T$; it follows from Assumption \ref{ass:1} that $T_+(x) \leq \max(x - 1,0)$, hence
$T_+^{-1}(t)\geq 1 + t$ for $t > 0$.
Let $\Phi_f^{(n)}(\cdot)$ stand for the cumulative distribution function of $\sqrt{n}\left( \bar\theta_j(f) - Pf \right)$.
Applying \eqref{eq:c1} to the monotone function $x\mapsto T\left( \frac{x- \sqrt{n}z}{\Delta}\right)$
and $Q(\cdot)=\Phi_f^{(n)}(\cdot) - \Phi \left(\cdot/\sigma(f)\right)$, we deduce that for any $f\in \mathcal F$,
\begin{multline}
\label{eq:decomp}
\left| \mathbb E \left( T\left( \sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta}\right) - T\left(  \frac{W(f) - \sqrt{n} z }{\Delta}  \right) \right) \right|
\\
\leq \int_0^\infty \left| Q\left( x: T_+\left( \frac{x - \sqrt{n}z}{\Delta} \right) \geq t\right) \right| dt + \int_0^\infty \left| Q\left( x: T_-\left( \frac{x - \sqrt{n}z}{\Delta} \right) \geq t\right) \right| dt.
\end{multline}
Inequality \eqref{eq:BE-main} implies that
\begin{multline}
\label{eq:key-ineq}
 \left| Q\left( x: T_+\left( \frac{x - \sqrt{n}z}{\Delta} \right) \geq t\right) \right| =  \left| Q\left( x: x \geq \Delta \, T_+^{-1}(t) + \sqrt{n}z \right) \right|
 \\
 \leq g_f\big( \Delta \, T_+^{-1}(t) + \sqrt{n}z,n\big) \leq
 g_f\left(\Delta\left( \frac{1}{2} + t \right),n \right)
 \end{multline}
where we used monotonicity of $g_f$ together with the inequalities $\sqrt{n}|z|\leq \frac{1}{2}\Delta$ and $T_+^{-1}(t)\geq 1 + t$ on the last step.
Integrating inequality \eqref{eq:key-ineq} from $0$ to $\infty$, we see that
\begin{equation*}
\int_0^\infty \left| Q\left( x: T_+\left( \frac{x - \sqrt{n}z}{\Delta} \right) \geq t\right) \right| dt \leq
\int_{0}^{\infty} g_f\left(\Delta\left( \frac{1}{2} + t \right),n \right) dt = G_f(n,\Delta).
\end{equation*}
Similarly, $\int_0^\infty \left| Q\left( x: T_-\left( \frac{x - \sqrt{n}z}{\Delta} \right) \geq t\right) \right| dt \leq G_f(n,\Delta)$, hence the conclusion follows from \eqref{eq:decomp}.
\end{proof}

\begin{lemma}
\label{lemma:step3}
Let $\varepsilon>0$ be such that $\varepsilon \leq 0.045$,
and set
\[
z_1 = -\frac{\varepsilon}{ 0.09}\, \frac{\max\left(\Delta,\sigma(\mathcal F) \right)}{\sqrt{n}}.
\]
Then for all $f\in \mathcal F$,
\begin{equation*}
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z_1 }{\Delta} \right) > \varepsilon.
\end{equation*}
\end{lemma}
\begin{proof}
For any bounded function $h$ such that $h(-x)=-h(x)$ and $h(x)\geq 0$ for $x\geq 0$, and any $z\leq 0$,
\[
\int_\mathbb R h(x-z)\phi_\sigma(x) dx = \int_0^\infty h(x)\left( \phi_\sigma(x+z) - \phi_\sigma(-x+z)\right)dx \geq 0,
\]
where $\phi_\sigma(x) = (2\pi\sigma)^{-1/2}e^{-x^2/2\sigma^2}$.
Recall that $H'(x) \geq \frac{x}{2}$ for $0\leq x\leq 2$, and take
\[
h(x) := \rho'(x) - \frac{x}{2} I\{|x|\leq 2 \} = H'(x) - \frac{x}{2} I\left\{ |x|\leq 2\right\}.
\]
Observe that $h(x)\geq 0$ for $x\geq 0$ by assumptions on $\rho$, hence for any $j$,
\begin{multline}
\label{eq:exp0}
 \mathbb E \rho'\left( \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right)
  = \frac{1}{2}\mathbb E\left(  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} I\left\{ \left|  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right| \leq 2 \right\}\right)
 + \mathbb E h\left(  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right)
 \\
\geq \max\left( \frac{1}{2}\mathbb E\left(  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} I\left\{ \left|  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right| \leq 2 \right\}\right),
\, \mathbb E h\left(  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right) \right),
\end{multline}
where we used the fact that both terms are nonnegative. Next, we will find lower bounds for each of the terms in the maximum above, starting with the first.

\textbf{(1)} Consider two possibilities: (a) $\Delta < \sigma(f)$ and (b) $\Delta \geq \sigma(f)$. In the first case, we will use the trivial lower bound $\mathbb E\left(  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} I\left\{ \left|  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right| \leq 2 \right\}\right) \geq 0$.
The main focus will be on the second case. To this end, note that $Z:=\frac{W(f)}{\sigma(f)}\sim N(0,1)$, hence
\begin{multline}
\label{eq:exp1}
\frac{1}{2}\mathbb E\left(  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} I\left\{ \left|  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right| \leq 2\right\}\right)
\\
= \frac{\sigma(f)}{2\Delta}\mathbb E \left( Z \,I\left\{ \left| Z - \frac{\sqrt{n}\, z_1}{\sigma(f)} \right|\leq 2\frac{\Delta}{\sigma(f)} \right\} \right) -
\frac{\sqrt{n}\, z_1}{2\Delta}\pr{\left| Z - \frac{\sqrt{n}\, z_1}{\sigma(f)} \right|\leq 2\frac{\Delta}{\sigma(f)}}.
\end{multline}
Direct computation shows that for any $a\in \mathbb R, \ t>0$,
\begin{equation}
\label{eq:exp}
\Big| \mathbb E \left( Z \, I\left\{ |Z-a|\leq t\right\}\right) \Big| = \frac{1}{\sqrt{2\pi}}e^{-\frac{a^2+t^2}{2}} \left| e^{at} - e^{-at} \right|.
\end{equation}
Take $a= - \frac{z_1\sqrt{n}}{\sigma(f)}$, $t=2\frac{\Delta}{\sigma(f)}$, and observe that assumptions of the Theorem imply the inequality $|a| \leq \frac{t}{4}$.
Minimum of the function $a\mapsto a^2 + t^2 - 2|a|t$ over the set $0\leq a\leq t/4$ is attained at $a=t/4$, implying that
$a^2 + t^2 - 2|a| t \geq \frac{9}{16}t^2>\frac{t^2}{2}$.
Combining this with \eqref{eq:exp}, we deduce that
\begin{equation*}
\Big| \mathbb E \left( Z \, I\left\{ |Z-a|\leq t\right\}\right) \Big| \leq  \frac{1}{\sqrt{2\pi}}e^{-t^2/4} e^{-|at|}\left| e^{at} - e^{-at}\right|
= \frac{e^{-t^2/4}}{\sqrt{2\pi}}\left( 1 - e^{-2|at|}\right)\leq \frac{e^{-t^2/4}}{\sqrt{2\pi}}\cdot 2|at|,
\end{equation*}
hence
\begin{equation*}
\Bigg| \frac{\sigma(f)}{2\Delta}\mathbb E \left( Z \,I\left\{ \left| Z - \frac{\sqrt{n}\, z_1}{\sigma(f)} \right|\leq 2\frac{\Delta}{\sigma(f)} \right\} \right) \Bigg| \leq \frac{2}{\sqrt{2\pi}} \left|\frac{z_1\sqrt{n}}{\sigma(f)}\right| e^{-\frac{\Delta^2}{\sigma^2(f)}}
= \frac{2}{\sqrt{2\pi}} \left|\frac{z_1\sqrt{n}}{\Delta}\right| \frac{\Delta}{\sigma(f)}e^{-\frac{\Delta^2}{\sigma^2(f)}}.
\end{equation*}
Moreover, since $|z_1|\leq \frac{1}{2}\frac{\Delta}{\sqrt{n}}$ by assumptions of the lemma, it follows that
\[
\pr{\left| Z - \frac{\sqrt{n}\, z_1}{\sigma(f)} \right|\leq 2\frac{\Delta}{\sigma(f)}} \geq
\pr{\left| Z\right|\leq \frac{3\Delta}{2\sigma(f)} }\geq 1 - 2\Phi(-3/2)>0.86.
\]
Together with \eqref{eq:exp0}, \eqref{eq:exp1}, the last display yields that
\[
 \mathbb E \rho'\left( \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right) > \left|\frac{0.86}{2} \frac{z_1\sqrt{n}}{\Delta} \right| -
 \frac{2}{\sqrt{2\pi}}\left|\frac{z_1\sqrt{n}}{\Delta}\right| \frac{\Delta}{\sigma(f)} e^{-\frac{\Delta^2}{\sigma^2(f)}}.
\]
As $x\mapsto x e^{-x^2}$ is decreasing for $x\geq 1/\sqrt{2}$, one easily checks that $\frac{\Delta}{\sigma(f)} e^{-\frac{\Delta^2}{\sigma^2(f)}}\leq e^{-1}$ as $\Delta \geq \sigma(f)$, hence
\begin{equation*}
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right) > \left( 0.43 -  \frac{2}{e\sqrt{2\pi}} \right)|z_1| \frac{\sqrt{n}}{\Delta} > 0.1364 |z_1| \frac{\sqrt{n}}{\Delta}.
\end{equation*}

\textbf{(2)} For the second term, we start with a simple inequality
\begin{multline*}
\mathbb E h\left(  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right) \geq \mathbb E \rho'\left(  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right) \,
I\left\{ \left|  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right| > 2 \right\}
\\
\geq \underbrace{\rho'(2)}_{\geq 1} \, \mathbb E\left( I\left\{ \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} > 2 \right\} - I\left\{ \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} < -2 \right\} \right)
\end{multline*}
which follows from the definition of $h$ and assumptions on $\rho$.
Again, we consider two possibilities: (a) $\Delta < \sigma(f)$ and (b) $\Delta \geq \sigma(f)$. In case (b), we use the trivial bound
\[
\mathbb E\left( I\left\{ \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} > 2 \right\} - I\left\{ \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} < -2 \right\} \right) \geq 0.
\]
In the first case, we see that
\begin{multline*}
\Pr\left( \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \geq 2 \right) - \Pr\left( \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \leq -2  \right)
\\
= \Pr\left( Z \geq \frac{\sqrt{n}z_1}{\sigma(f)} + 2\frac{\Delta}{\sigma(f)} \right) -
\Pr\left( Z \leq \frac{\sqrt{n}z_1}{\sigma(f)} - 2\frac{\Delta}{\sigma(f)}\right)
\\
= \Pr\left( Z \in \left[ \frac{\sqrt{n}\,z_1}{\sigma(f)} + 2\frac{\Delta}{\sigma(f)}, -\frac{\sqrt{n}\, z_1}{\sigma(f)} + 2\frac{\Delta}{\sigma(f)} \right]\right).
\end{multline*}
Lemma \ref{lemma:normal} implies that
\begin{multline*}
\Pr\left( Z \in \left[ \frac{\sqrt{n}\, z_1}{\sigma(f)} + 2\frac{\Delta }{\sigma(f)}, -\frac{\sqrt{n}\, z_1}{\sigma(f)} + 2\frac{\Delta}{\sigma(f)} \right]\right) \geq 2 e^{-\frac{2\Delta^2}{\sigma^2(f)}} \Pr\left( Z\in \left[0, \frac{\sqrt{n}|z_1|}{\sigma(f)}\right] \right)
\\
\geq 2 e^{-2}\Pr\left( Z\in \left[0, \frac{\sqrt{n}|z_1|}{\sigma(f)}\right] \right),
\end{multline*}
where we used the fact that $\Delta < \sigma(f)$ by assumption.
Finally, Lemma \ref{lemma:quantile} implies that
\[
\Pr\left( Z\in \left[0, \frac{\sqrt{n}|z_1|}{\sigma(f)}\right] \right) > \frac{1}{3}\frac{\sqrt{n}|z_1|}{\sigma(f)}
\]
whenever $|z_1|\leq 0.99 \frac{\sigma(f)}{\sqrt{n}}$.
In conclusion, we demonstrated that in case (a)
\[
\mathbb E h\left(  \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right) > \frac{2e^{-2}}{3} |z_1|\frac{\sqrt{n}}{\sigma(f)} > 0.09 |z_1|\frac{\sqrt{n}}{\sigma(f)}.
\]
Combining results \textbf{(1)} and \textbf{(2)} for both terms in the maximum \eqref{eq:exp0}, we see that for any $\Delta > 0$,
\begin{equation}
\label{eq:finalBound}
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n}\, z_1 }{\Delta} \right) > \mathrm{min}\left( 0.1364,0.09\right) |z_1| \frac{\sqrt{n}}{\max(\Delta,\sigma(f))}
= 0.09 |z_1| \frac{\sqrt{n}}{\max(\Delta,\sigma(f))}
\end{equation}
given that $|z_1|\leq \frac{1}{2} \frac{\max\left(\Delta ,\sigma(f)\right)}{\sqrt{n}}$.
Let $\varepsilon>0$. It is easy to check that setting
\begin{equation*}
z_1 = -\frac{1}{0.09} \max\left(\Delta,\sigma(f)\right) \frac{\varepsilon}{\sqrt{n}}
\end{equation*}
yields, in view of \eqref{eq:finalBound}, that
\[
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) > \varepsilon,
\]
as long as condition $|z_1|\leq \frac{1}{2}\frac{\max\left(\Delta,\sigma(f)\right)}{\sqrt{n}}$ holds for all $j$. The latter is equivalent to requirement that
$\varepsilon \leq \frac{0.09}{2}$.
\end{proof}

\subsection{Proof of Theorem \ref{th:unif-U}.}
\label{proof:unif-U}

Suppose $z_1,z_2$ are such that on an event of probability close to $1$, $U'_{N,n}(z_1;f) > 0$ and $U'_{N,n}(z_2;f) < 0$ for all $f\in \mathcal F$ simultaneously.
For such $z_1,z_2$, it is easy to see that $\widetilde \theta^{(k)}(f) - Pf \in (z_1,z_2)$ for all $f\in \mathcal F$ on the corresponding event.
Observe that
\begin{multline*}
U'_{N,n}(z;f) = \frac{1}{N!}\sum_{(i_1,\ldots,i_N)\in \pi_N} T_{i_1,\ldots,i_N}(z;f) - \mathbb E \, T_{i_1,\ldots,i_N}(z;f)
\\
+ \mathbb E  \rho'\left(\sqrt{n}\,\frac{\bar \theta(f;\{1,\ldots,n\}) - Pf - z}{\Delta}\right)
- \mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right)  +
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right).
\end{multline*}
The rest of the proof mimics the steps in the proof of Theorem \ref{th:unif}.
Namely, we will find positive $\varepsilon_1, \varepsilon_2$ such that
\begin{equation}
\label{eq:eps-1.2}
\inf_{f\in \mathcal F} \frac{1}{N!}\sum_{(i_1,\ldots,i_N)\in \pi_N} T_{i_1,\ldots,i_N}(z;f) - \mathbb E \, T_{i_1,\ldots,i_N}(z;f)
=  \inf_{f\in \mathcal F} \left( U'_{N,n}(z;f) - \mathbb E U'_{N,n}(z;f) \right) \geq -\varepsilon_1
\end{equation}
with high probability and
\[
\inf_{f\in \mathcal F} \mathbb E  \rho'\left(\sqrt{n}\,\frac{\bar \theta(f;\{1,\ldots,n\}) - Pf - z}{\Delta}\right)
- \mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \geq -\varepsilon_2
\]
and will choose $z$ such that $\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right)>\varepsilon_1+\varepsilon_2$.

In view of \eqref{eq:U-concentr} and the fact that $\|\rho'\|_\infty\leq 2$, $\varepsilon_1$ can be chosen as
\[
\varepsilon_1 = 2\mathbb E\sup_{f\in \mathcal F}\Big( T_{1,\ldots,N}(z;f) - \mathbb E T_{1,\ldots,N}(z;f) \Big)
+ \frac{\sigma(f)}{\Delta}\sqrt{\frac{2s}{k}} + \frac{16s}{3k}
\]
for which inequality \eqref{eq:eps-1.2} holds with probability at least $1-e^{-s}$.
It is also easy to see, following the symmetrization-contraction argument of Lemma \ref{lemma:step1}, that
\[
\mathbb E \sup_{f\in \mathcal F}\Big( T_{1,\ldots,N}(z;f) -\mathbb E T_{1,\ldots,N}(z;f)\Big) \leq
\frac{8}{\Delta \sqrt{k}} \, \mathbb E\sup_{f\in \mathcal F} \left|\frac{1}{\sqrt{nk}} \sum_{j=1}^{nk} \left( f(X_j) - Pf \right)\right|.
\]
Lemma \ref{lemma:step2} implies that
\[
\sup_{f\in \mathcal F} \left| \mathbb E  \rho'\left(\sqrt{n}\,\frac{\bar \theta(f;\{1,\ldots,n\}) - Pf - z}{\Delta}\right)
- \mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \right| \leq 2\sup_{f\in\mathcal F} G_f(n,\Delta):= \varepsilon_2.
\]
Finally, equation \eqref{eq:finalBound} in the proof of Lemma \ref{lemma:step3} yields that, for $z<0$,
\[
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n}\, z }{\Delta} \right) > 0.09 |z| \frac{\sqrt{n}}{\max(\Delta,\sigma(f))}
\]
as long as $|z|\leq \frac{1}{2}\frac{\max\left(\Delta,\sigma(f)\right)}{\sqrt{n}}$.
Hence, choosing $z_1:= -\frac{1}{0.09}\frac{\max\left(\Delta,\sigma(\mathcal F)\right)}{\sqrt{n}}\left( \varepsilon_1 + \varepsilon_2\right)$ implies that $U'_{N,n}(z_1;f)>0$ for all $f\in \mathcal F$ simultaneously with probability at least $1-e^{-s}$. Similarly, $z_2=-z_1$ satisfies $U'_{N,n}(z_2;f)<0$ for all $f\in \mathcal F$ with the same probability, and the claim follows.

\subsection{Proof of Theorem \ref{th:unif2}.}
\label{proof:unif2}

The proof closely follows the steps of the proof of Theorem \ref{th:unif}.
All the probabilities below are evaluated conditionally on $N_J$ (see section \ref{sec:adversary} for the definition).
Recall that
\[
G_k(z;f) =  \frac{1}{\sqrt k} \sum_{j=1}^k \rho'\left( \sqrt{n}\,\frac{ (\bar \theta_j(f) - Pf) - z}{\Delta} \right).
\]
We are looking for $z_1,z_2\in \mathbb R$ with $|z_1|,\, |z_2|$ as small as possible such that on an event of probability close to $1$, $G_k(z_1;f) > 0$ and $G_k(z_2;f) < 0$ for all $f\in \mathcal F$ simultaneously.
Observe that
\[
G_k(z;f) = \frac{1}{\sqrt k} \sum_{j\in J} \rho'\left( \sqrt{n}\,\frac{ (\bar \theta_j(f) - Pf) - z}{\Delta} \right) +
\frac{1}{\sqrt k} \sum_{j\notin J}\rho'\left( \sqrt{n}\,\frac{ (\bar \theta_j(f) - Pf) - z}{\Delta} \right).
\]
The second sum can be estimated as
\[
\left| \frac{1}{\sqrt k} \sum_{j\notin J}  \rho'\left( \sqrt{n}\,\frac{ (\bar \theta_j(f) - Pf) - z}{\Delta} \right) \right|
\leq \|\rho'\|_\infty \sum_{j\notin J}\frac{1}{\sqrt k} \leq 2 \frac{\mathcal O}{\sqrt k}.
\]
where we used the fact that $\|\rho'\|_\infty \leq 2$.
For the first sum, we proceed as in the proof of Theorem \ref{th:unif} and decompose it as
\begin{multline*}
\frac{1}{\sqrt k} \sum_{j\in J}  \rho'\left( \sqrt{n}\,\frac{ (\bar \theta_j(f) - Pf) - z}{\Delta} \right)
\\
 = \frac{1}{\sqrt k} \sum_{j\in J}  \left(  \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) - \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)  \right)
 \\
+ \frac{1}{\sqrt k} \sum_{j\in J}  \left( \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) -
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \right)
\\
+\frac{1}{\sqrt k}  \sum_{j\in J} \mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right).
\end{multline*}
It follows from Lemma \ref{lemma:step1} that for any $z\in \mathbb R$,
\begin{multline*}
\inf_{f\in \mathcal F} \frac{1}{\sqrt k}\sum_{j\in J} \left(  \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) - \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)  \right)  \\
=\sqrt{\frac{|J|}{k}} \inf_{f\in \mathcal F} \frac{1}{\sqrt{|J|} }\sum_{j\in J}  \left(  \rho'\left( \sqrt{n}\frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) - \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right)  \right)
\geq -\varepsilon_1
\end{multline*}
with probability at least $1 - e^{-s}$, where
\[
\varepsilon_1 = \sqrt{\frac{|J|}{k}}\left( \frac{8 }{\Delta\sqrt{N_J}} \, \mathbb E\sup_{f\in \mathcal F} \sum_{j=1}^{N_J} \left( f(X_j) - Pf \right)
+ \frac{\sigma(\mathcal F)}{\Delta}\sqrt{2s} + \frac{16}{3}\frac{s}{\sqrt{|J|}} \right).
\]
Next, Lemma \ref{lemma:step2} implies that
\begin{multline*}
\inf_{f\in \mathcal F}  \sum_{j\in J} \frac{1}{\sqrt k}\left( \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) -
\mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \right)
\\
= \sqrt{\frac{|J|}{k}} \inf_{f\in \mathcal F} \sum_{j\in J} \frac{1}{\sqrt{|J|}} \left( \mathbb E\rho'\left(\sqrt{n} \frac{(\bar \theta_j(f) - Pf) - z}{\Delta} \right) - \mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) \right)
\leq \varepsilon_2,
\end{multline*}
where $\varepsilon_2 = 2\frac{|J|}{\sqrt{k}}\sup_{f\in \mathcal F}G_f(n,\Delta)$.
Finally we will choose $z_1<0$ such that for all $f\in \mathcal F$,
\begin{equation*}
\frac{1}{\sqrt k}\sum_{j\in J}  \mathbb E \rho'\left( \frac{W(f) - \sqrt{n} z }{\Delta} \right) > \varepsilon_1 + \varepsilon_2 +
2 \frac{\mathcal O}{\sqrt k}.
\end{equation*}
Lemma \ref{lemma:step3} implies that it suffices to take
\[
z_1 = -\frac{1}{0.09} \frac{\widetilde \Delta}{\sqrt n} \left( \varepsilon_1 + \varepsilon_2 + 2 \frac{\mathcal O}{\sqrt k}\right)\frac{\sqrt k}{|J|}
\geq -C \frac{\widetilde \Delta}{\sqrt n}\frac{\varepsilon_1 + \varepsilon_2 + \mathcal O/\sqrt{k} }{\sqrt k}.
\]
To get the final form of the bound, observe that  $\mathbb E\sup_{f\in \mathcal F} \sum_{j=1}^{N_J} \left( f(X_j) - Pf \right) \leq
\mathbb E\sup_{f\in \mathcal F}  \sum_{j=1}^{N} \left( f(X_j) - Pf \right)$ due to Jensen's inequality and that $N_J\geq N/2$ by assumption.
	\begin{comment}

In view of the inequalities
\begin{align*}
& N_J \geq \frac{kn}{2}
\\
& \mathbb E\sup_{f\in \mathcal F} \left| \sum_{j=1}^{N_J} \left( f(X_j) - Pf \right)\right| \leq
\mathbb E\sup_{f\in \mathcal F} \left| \sum_{j=1}^{N} \left( f(X_j) - Pf \right)\right|,  \text{  (Jensen's inequality) }
\end{align*}
this assumption on $\varepsilon$ is implied by condition \eqref{eq:cond3}.
	\end{comment}
Similarly, setting $z_2=-z_1$ guarantees that $G_k(z_2;f)<0$ for all $f\in \mathcal F$ with probability at least $1 - e^{-s}$, hence the claim follows.

\subsection{Proof of Lemma \ref{lemma:BE-nonunif}.}
\label{proof:BE-nonunif}

For brevity, set $Y:=f(X) - Pf$, let $Y_1,\ldots,Y_n$ be i.i.d. copies of $Y$, and let $W(f)$ have normal distribution $N(0,\sigma^2(f))$. Theorem 2.2 in \cite{chen2001non} implies that for an absolute constant $C>0$ and any $t\in \mathbb R$,
\begin{multline}
\label{eq:stein}
\left| \pr{\frac{1}{\sqrt{n}}\sum_{j=1}^n Y_j \geq t } - \pr{W(f) \geq t} \right| \leq g_f(t,n)
\\
=C \left( \frac{\mathbb E Y^2 \, I\left\{ \frac{|Y|}{\sigma\sqrt{n}} >  1+|t/\sigma| \right\}}{\sigma^2 (1+|t/\sigma|)^2} + \frac{1}{\sqrt{n}}
\frac{\mathbb E |Y|^3 \, I\left\{ \frac{|Y|}{\sigma\sqrt{n}} \leq 1+|t/\sigma|\right\}}{\sigma^3 (1+|t/\sigma|)^3}\right).
\end{multline}
It is clear that $g_f(s,n)<g_f(t,n)$ for $t<s$,  $g_f(t,m)<g_f(t,n)$ for $n<m$, and that $g_f(t,n)\to 0$ as $|t|\to\infty$. To show that $g_f(t,n)$ converges to $0$ as $n\to\infty$, let $\{a_n\}_{n\geq 1}$ be any sequence such that $a_n\to\infty$, $a_n\leq \sqrt{n}$ and $a_n=o(\sqrt{n})$. Then
\begin{multline*}
\frac{1}{\sqrt n}\mathbb E |Y|^3 \, I\left\{ |Y| \leq \sigma\sqrt{n}(1+|t/\sigma|)\right\} \leq
\frac{1}{\sqrt n}\Big( \mathbb E|Y|^3 \, I\left\{ |Y| \leq \sigma \cdot a_n(1+|t/\sigma|)\right\}
\\
+ \mathbb E|Y|^3 \, I\left\{ \sigma \cdot a_n(1+|t/\sigma|) \leq |Y| \leq \sigma\cdot\sqrt{n}(1+|t/\sigma|)\right\}\Big)
\\
\leq (\sigma + |t|)\left( \frac{a_n}{\sqrt{n}} \, \mathbb EY^2 + \mathbb E Y^2 I\left\{ |Y| \geq \sigma \cdot a_n(1+|t/\sigma|)\right\}\right),
\end{multline*}
hence
\begin{equation*}
g_f(t,n) \leq \frac{C}{(\sigma+|t|)^2}\left( \mathbb E Y^2 \, I\left\{ |Y| >  a_n\left(\sigma + |t| \right)\right\} + \frac{a_n}{\sqrt n}\mathbb EY^2 \right)
\end{equation*}
where the latter expression converges to $0$ as $n\to\infty$.
Next, assume that $\mathbb E|Y|^{2+\delta}<\infty$ for some $\delta\in(0,1]$.
Applying H\"{o}lder's inequality followed by Markov's inequality, we deduce that
\begin{multline*}
\mathbb E \left(\frac{X^2}{\sigma^2} \, I\left\{ \frac{|X|}{\sigma\sqrt{n}} >  1+|t/\sigma| \right\} \right)\leq
\left(\mathbb E |X/\sigma|^{2+\delta}\right)^{2/(2+\delta)} \left( \pr{\frac{|X|}{\sigma\sqrt{n}} > 1+ |t/\sigma|} \right)^{\delta/(2+\delta))}
\\
\leq \frac{\mathbb E |X/\sigma|^{2+\delta}}{n^{\delta/2}(1+|t/\sigma|)^{\delta}}.
\end{multline*}
Moreover, it is clear that
\begin{equation*}
\mathbb E \left( \frac{|X|^3}{\sigma^3} \, I\left\{ \frac{|X|}{\sigma\sqrt{n}} \leq 1+|t/\sigma|\right\} \right) \leq \left( \sqrt{n}(1+|t/\sigma|)\right)^{1-\delta}\mathbb E |X/\sigma|^{2+\delta}.
\end{equation*}
Combining these inequalities with \eqref{eq:stein}, we deduce the bound \eqref{eq:g_f} for $g_f(t,n)$.
Finally, an upper bound for $G_f(n)$ follows by integrating the inequality \eqref{eq:g_f}.

\section{Supplementary results.}
\label{section:supplement}

\begin{lemma}
\label{lemma:quantile}
Assume that $0\leq \alpha \leq 0.33$ and let $z(\alpha)$ be such that $\Phi(z(\alpha))-1/2 = \alpha$.
Then $z(\alpha)\leq 3\alpha$.
\end{lemma}
\begin{proof}
It is a simple numerical fact that whenever $\alpha \leq 0.33$, $z(\alpha)\leq 1$; indeed, this follows as $\Phi(1)\simeq 0.8413>1/2+0.33$.
Since $e^{-y^2/2}\geq 1 - \frac{y^2}{2}$, we have
\begin{equation}
\label{eq:05}
\sqrt{2\pi} \alpha = \int_0^{z(\alpha) } e^{-y^2/2} dy
\geq z(\alpha) - \frac{1}{6}\left( z(\alpha) \right)^3
\geq \frac{5}{6} z(\alpha),
\end{equation}
Equation \eqref{eq:05} implies that
$z(\alpha) \leq \frac{6}{5}\sqrt{2\pi} \, \alpha$.
Proceeding again as in \eqref{eq:05}, we see that
\begin{equation*}
\sqrt{2\pi} \alpha \geq
z(\alpha) - \frac{1}{6}\left( z(\alpha) \right)^3
\\
\geq
z(\alpha) - \frac{12\pi}{25}\alpha^2 z(\alpha)
\\
\geq z(\alpha) \left( 1 - 1.51 \, \alpha^2 \right),
\end{equation*}
hence $z(\alpha) \leq \frac{\sqrt{2\pi}}{1 - 1.51 \, \alpha^2}\, \alpha.$
The claim follows since $\alpha \leq 0.33$ by assumption, and $ \frac{\sqrt{2\pi}}{1 - 1.51 \cdot 0.33^2}<3$.
\end{proof}

The following fact is well known; we present a short proof for reader's convenience.
\begin{lemma}
\label{lemma:normal}
Let $\mathcal A\subset \mathbb R$ be symmetric, meaning that $\mathcal A=-\mathcal A$, and let $Z\sim N(0,1)$. Then for all $x\in \mathbb R$,
\[
\pr{Z\in A - x}\geq e^{-x^2/2}\,\pr{Z\in A}.
\]
\end{lemma}
\begin{proof}
Observe that
\begin{align*}
\pr{Z\in A} & = \int_\mathbb R I\{z\in A\} \frac{1}{\sqrt{2\pi}}e^{-z^2/2} dz = e^{x^2/2}\int_\mathbb R I\{z\in A\} e^{-xz/2}e^{xz/2}\frac{1}{\sqrt{2\pi}}e^{-z^2/2} e^{-x^2/2} dz
\\
& \leq e^{x^2/2} \sqrt{ \int_\mathbb R I\{z\in A\} \frac{1}{\sqrt{2\pi}}e^{-(z-x)^2/2}dz}\sqrt{ \int_\mathbb R I\{z\in A\} \frac{1}{\sqrt{2\pi}}e^{-(z+x)^2/2}dz}
\\
& =  e^{x^2/2} \int_\mathbb R I\{z\in A\} \frac{1}{\sqrt{2\pi}}e^{-(z-x)^2/2}dz = e^{x^2/2}\,\pr{Z\in A - x},
\end{align*}
and the claim follows.
\end{proof}

\begin{lemma}
\label{lemma:variance}
Let $\rho$ satisfy Assumption \ref{ass:1}. Then for any random variable $Y$ with $\mathbb EY^2<\infty$,
\[
\mbox{Var}\left(\rho'(Y)\right) \leq \mbox{Var}\left( Y \right).
\]
\end{lemma}
\begin{proof}
The function $u(t)=t-\rho'(t) - c$ is nondecreasing for any $c\in \mathbb R$ by Assumption \ref{ass:1}, hence for any $s\in \mathbb R$, there exists $t(s)$ such that $u(t)\geq s$ iff $t\geq t(s)$. Next, consider $\tilde u(t) = t - \mathbb EY - (\rho'(t) - \mathbb E\rho'(Y))$, and let $t_0$ be such that $\tilde u(t)\geq 0$ for $t\geq t_0$ and $\tilde u(t) \leq 0$ when $t \leq t_0$.
For any $x,y\in \mathbb R$, $x^2 - y^2\geq 2y(x-y)$. Letting $x=t - \mathbb EY$ and $y = \rho'(t) - \mathbb E\rho'(Y)$, we obtain
\begin{equation*}
(t - \mathbb EY)^2 - (\rho'(t) - \mathbb E\rho'(Y))^2 \geq 2(\rho'(t) - \mathbb E\rho'(Y))\left(t - \mathbb EY - (\rho'(t) - \mathbb E\rho'(Y))\right).
\end{equation*}
Consider two cases: (a) $t\geq t_0$ and (b) $t<t_0$. In the first case, $\rho'(t) - \mathbb E\rho'(Y) \geq \rho'(t_0) - \mathbb E \rho'(Y)$ and $\left(t - \mathbb EY - (\rho'(t) - \mathbb E\rho'(Y))\right)\geq 0$, hence
\[
(t - \mathbb EY)^2 - (\rho'(t) - \mathbb E\rho'(Y))^2 \geq 2(\rho'(t_0) - \mathbb E\rho'(Y))\left(t - \mathbb EY - (\rho'(t) - \mathbb E\rho'(Y))\right).
\]
In the second case, $\rho'(t) - \mathbb E\rho'(Y) \leq \rho'(t_0) - \mathbb E \rho'(Y)$ and $\left(t - \mathbb EY - (\rho'(t) - \mathbb E\rho'(Y))\right)\leq 0$, hence again
\begin{equation}
\label{eq:convex}
(t - \mathbb EY)^2 - (\rho'(t) - \mathbb E\rho'(Y))^2 \geq 2(\rho'(t_0) - \mathbb E\rho'(Y))\left(t - \mathbb EY - (\rho'(t) - \mathbb E\rho'(Y))\right).
\end{equation}
Replacing $t$ by $Y$ in \eqref{eq:convex} and taking the expectation yields the result.
\end{proof}

\begin{lemma}
\label{lemma:minmax}
Let $p\in[2,3]$, and assume that $X\in \mathbb R^d$ has distribution $P$ from a class $\mathcal P$ of all distributions with bounded $p$-th moments of one-dimensional projections, meaning that $\sup_{\|v\|_2=1}\mathbb E_P\left| \dotp{X-\mathbb EX}{v}\right|^p \leq 1$.
Let $X_1,\ldots,X_N$ be a sample from $(1-\varepsilon)P + \varepsilon Q$ where $0\leq \varepsilon<1/2$, $P\in \mathcal P$ and $Q$ is an arbitrary distribution.
Then for any estimator $\widehat \mu(X_1,\ldots,X_N)$ of the mean $\mu(P)$,
\[
\sup_{P\in \mathcal P,Q} \pr{\|\widehat \mu - \mu\|_2 \geq c_1\left( \sqrt{\frac{\mbox{tr\,}(\Sigma)}{N}} \vee \varepsilon^{1-1/p} \right)} \geq c_2.
\]
where $\Sigma$ is the covariance matrix of $P$ and $c_1,c_2$ are absolute constants.
\end{lemma}
\begin{proof}
If $\varepsilon=0$, then it is well known that the minimax rate of estimating the mean is $\sqrt{\frac{\mbox{tr\,} \Sigma}{N}}$ (e.g. see the remark following Theorem 3 in \cite{lugosi2018near}).
Let's assume that $\varepsilon>0$ and suppose that $P_1,P_2$ are two distributions supported on $\left\{ \varepsilon^{-1/p},0,-\varepsilon^{1/p}\right\}$, namely,
$P_1(0) = P_2(0) = \frac{1-2\varepsilon}{1-\varepsilon},$ $P_1\left(\varepsilon^{-1/p}\right)=\frac{\varepsilon}{1-\varepsilon}$, $P_2\left( -\varepsilon^{-1/p}\right) = 0$,
$P_2\left( \varepsilon^{-1/p}\right)=0$, $P_2\left( -\varepsilon^{-1/p} \right)=\frac{\varepsilon}{1-\varepsilon}$.
Clealy, $P_1\in \mathcal P, \ P_2\in \mathcal P$, the means of $P_1, P_2$ are $\mu(P_1)=\frac{\varepsilon^{1-1/p}}{1-\varepsilon}$, $\mu(P_2)=-\frac{\varepsilon^{1-1/p}}{1-\varepsilon}$ respectively and $\left|\mu(P_1)-\mu(P_2)\right| = \frac{2\varepsilon^{1-1/p}}{1-\varepsilon}$.

Next, let $Q_1$ and $Q_2$ be Dirac measures, namely $Q_1=\delta_{\varepsilon^{-1/p}}$ and $ Q_2 = \delta_{-\varepsilon^{-1/p}}$.
Then it is easy to check that $(1-\varepsilon)P_1 + \varepsilon Q_2 = (1-\varepsilon) P_2 + \varepsilon Q_1 = \hat P$, hence, given samples from $\hat P$, it is impossible to distinguish between $P_1$ and $P_2$.
Conclusion now follows from Theorem 5.1 in \cite{chen2018robust}.
\end{proof}

\section*{Acknowledgements. }

Part of this work was completed during my visit to ENSAE ParisTech. I would like to thank Faculty members and students at ENSAE for their hospitality.

\bibliographystyle{imsart-nameyear}

redpajama_set_name: RedPajamaArXiv


text:
Q: On factorizationa of a cube $\,m^3 = ab$ I am doing my thesis on elliptic curves right now and in the meantime this lemma showed up:
Suppose $a$ and $b$ are integers such that $ab = m^3$ for some integer $m$. Let $d = \operatorname{gcd}(a,b)$, then we can write
\begin{equation}\label{}
a = d\cdot p_1^{r_1}\cdots p_t^{r_t}\cdot (\operatorname{integer})^3,
\end{equation}
where $p_i|d$ and $r_i \in \mathbb{Z}$.
So I tried taking a prime that does not divide $d$ and tried to show it must appear as a third power, however I couldn't figure it out. Any help would be appreciated!

A: As lulu noted, the order of any prime dividing $ab$ must be divisible by 3, because $ab=m^3$. Now the product above just results from the fact that we can break up the primes dividing $m$ into those which divide only $a$, those which divide both $a$ and $b$, and thus divide $d$, and those which divide only $b$. Only the first two categories contribute to our expression for $a$, obviously, then you need simply observe that if a prime occurs exclusively in $a$, then the order of the prime in $a$ must be the same as the order of the prime dividing $ab$, whence it must be divisible by 3.

A: Because for each prime $p$ that does not divide $b$ we have $v_p(a)= v_p(ab) = v_p(m^3)=3v_p(m)$.
We can clearly make the part that is not $dp_1^{r_1}\dots p_r^{r_t}$ equal to the product of all of the $p^{v_p(ab)}$ where $p$ is a prime not dividing $b$.

A: Hint $ $ Let $\, c_a := d p_1^{r_1}\cdots p_t^{r_t}$ be the product of all prime factors of $\,a\,$ which also divide $\,b,\,$ and similarly for $\,c_b\,$ and $\,b.\,$  Then $\,a = a' c_a,\ b = c' c_b,\,$ and $\,a',b', c_a c_b\,$ are pairwise coprime, therefore
$\, m^3 = ab = a'\, b'\, (c_a c_b)\,\Rightarrow\, a',b'$ are cubes too.

redpajama_set_name: RedPajamaStackExchange


Bug #5251: EventDispatcher : It's unable to clean up listener completely during dispatch event.
Bug #5745: Cocos console are conflicting when using Cocos2d-x and Cocos2d-js at the same time.
Bug #5762: ParticleSystemQuad::setTotalParticles() can't set a value larger than the initialized value.


Home All Products AlcoMate Prestige (AL-6000) breathalyzer Red Pro Kit- Replaceable Sensor Technology.
AlcoMate Prestige (AL-6000) Red Pro Kit- Replaceable Sensor Technology.
The AlcoMate Prestige™, AlcoMate Premuim™ and the TS200 Revo™ are the only breathalyzers in the world that has PRISM TECHNOLOGY™ this proprietary technology is Patented and exclusive to these models only, no other brand on the market has this technology.
The Advantage Of AlcoMate Brand Breathalyzers Patented Replaceable Sensor Technology.
PRISM™ technology is an exclusively patented feature only available with AlcoMate breath alcohol testers (US Patent No. 7,841,224 B2, also worldwide).
The AlcoMate Prestige™ was the first Semi- Conductor breathalyzer in the world that did not need calibration, you simply change the sensor module. If you are looking for a Fuel-Cell model, The AlcoMate Revo TS200™ is the only Fuel-Cell breathalyzer in the world that you can change the sensor module.
You can change the sensor as fast and easy as replacing a battery. Simply replace with a new Pre-Calibrated sensor module. Now your breathalyzer is like new again, there is no need to send this unit in for a calibration service.
Since this proprietary sensor technology is patented there is no other brand of breathalyzer on the market that has this replaceable sensor technology. If you purchase a competitors brand you will have to mail your breathalyzer in for a calibration service and wait 4-6 weeks for it to return verses changing the sensor in a few seconds.
Sensor life is between 200-300 tests and this unit also includes a sensor replacement indicator. This unit also has a test counter integrated into the memory.
"Professional Grade " NO calibration needed, just replace the sensor every 200-300 tests or 9-12 months. Includes Sensor replacement indicator, all sensors are pre-calibrated for immediate use.
DOT and NHTSA Approved!- FDA Certified!- US COAST GUARD APPROVED!
Large 3 Digit LCD Display.
One Way- Air Flow Mouthpieces.
Range: 0.00% to 0.40% BAC (5 times the limit of 0.08 BAC) not 0.040 BAC.
Blow time: 5.0 seconds- DOT. and NHTSA Approved (Exceeds D.O.T. and NHTSA standards).
BREATHCHECK ERROR Technology: You will never have to GUESS if enough air has been blown into the unit, the unit will warn you with an audible and digital warning.
Pressure sensor system: Which lets you know if the subject has not blown long enough into the unit.
Test Counter: Includes number of tests indicator.
Audible Function: 3-step beep warning of alcohol detection with LCD lighted display for day or night time use.
Warranty: One year warranty through AlcoTester.com!
Please watch this video to see how easy it is to replace the patented sensor module.
Take $10 Off Sale Price + Free Shipping Today Only!
Very nice video demo, explained how easy it is to use. I thought these would be hard to use since a friend of mine owns another brand and she was complaning how difficult it was to operate but this video shows just how simple it is. Now she is getting the same one after using mine and she also said hers needs calibration and this does not I had no idea what that was. I found out that this sensor can be replaced and the other breathalyzers have to be sent in. I watched the other video after she mentioned it, I didnt see the other when I orderd it but now I see it. so it is even better than I thought yes, I would recommend.
I am a mother of 2 teenagers and they know that I am fully prepared on those late nights they come strolling in. Very easy to use and it will never lie to me!
I am very pleased with service received. Response from order to shipping to receipt was very fast. Thank You AlcoTester.com for your excellent products and service.


Computers were just the medium, when users surfed the web nearly a decade before. Hence, during that time, the sites were created to fit the resolution of the computer screen. But nowadays, the demand of mobiles, smartphones and tablets is increasing day by day because of a wide range of extraordinaryfeatures offered by them. The time has changed the way you surf the internet. It is the possibility that you want to make use of mobiles or tablets to surf the internet for any of the purposes. This has given the birth to responsive website designing.
These days, the use of responsive sites is increasing daily because almost all the business owners have understood the need of creating the sites, which can work properly on the technological devices other than the computers. If you will not use this technology to create your site, then it mightlack behind the traffic and sales. People need to understand the importance of responsive web designs for their sites and try to implement them to stay ahead of others. With the responsive web design, you can give an option to your customers to search on the web, while using either mobiles or computers in recent times.
Web designers also need to learn all the techniques and methods used in this latest kind of technology. In order to meet the needs and preferences of business owners, we have designed responsive web design training programs to help them in any manner. With the training courses, you can easily learn the skills of responsive designing. We are the experts, who can make the responsive web designing study easier and quicker for you. It is all because of the experience and knowledge we have.
We have a team of professionals, including web designers, developers and many others, who can create unique and attractive sites as per the responsive designing. Our professionals create the responsive designs so that you can increase your sales and business to lead others. When you want to implement the responsive designing, then you need to understand the process, which includes updation, the management of SEO and many others. It is all a time consuming procedure. So, you can make the process easier and faster by experiencing our training courses, especially designed for beginners and even the professionals.


text:
AU Optronics executive sentenced for LCD price-fixing
By Grant Gross
Senior Editor, IDG News Service | PT
A former executive with AU Optronics was sentenced Monday to serve two years in prison and pay a $50,000 fine for participating in a worldwide LCD screen price-fixing conspiracy, the U.S. Department of Justice said.
Shiu Lung Leung, former senior manager of AU Optronics' desktop display business group, was sentenced for price fixing in U.S. District Court for the Northern District of California.
AU Optronics, based in Hsinchu, Taiwan, and its U.S. subsidiary, AU Optronics America, headquartered in Milpitas, California, were found guilty in March 2012, for participating in the thin-film transistor-liquid crystal display (TFT-LCD) price-fixing conspiracy, after an eight-week trial. Also found guilty were former AU Optronics President Hsuan Bin Chen and former AU Optronics Executive Vice President Hui Hsiung.
A trial for Leung then ended in a mistrial. Monday's sentencing followed a three-week retrial that started in November and resulted in Leung's conviction. Leung's lawyer wasn't immediately available for comment on the sentencing.
The original indictment charged that AU Optronics participated in the worldwide price-fixing conspiracy from September 2001 to December 2006, with the U.S. subsidiary joining the conspiracy as early as spring 2003. The indictment charged that Leung participated in that conspiracy starting in May 2002.
LCD panels affected by the conspiracy were a major component in flat-panel computer monitors, notebook computers, and flat-screen televisions sold in the U.S., the DOJ said. The conspirators fixed the prices of LCD panels during monthly meetings with their competitors, secretly held in hotel conference rooms, karaoke bars and tea rooms around Taiwan.
"These international price-fixers caused consumers to pay inflated prices for their computer monitors, notebook computers and televisions," Assistant Attorney General Bill Baer, in charge of the DOJ's Antitrust Division, said in a statement. "Prison sentences for culpable executives, combined with substantial fines against corporate wrongdoers, are the most effective deterrents for protecting consumers from this kind of illegal cartel behavior."
Eight companies have been convicted of charges arising out of the DOJ's ongoing investigation into LCD price fixing. They have been sentenced to pay criminal fines of $1.39 billion. The DOJ has brought charges against 22 executives, and 13 of them have been convicted and sentenced to serve prison terms ranging from six to 36 months.
Grant Gross edits and assigns stories and writes about technology and telecom policy in the U.S. government for the IDG News Service. He is based outside of Washington, D.C.

redpajama_set_name: RedPajamaCommonCrawl


Productivity 101 (Day 24): Free Prizes!
You guessed it: a contest!
Do you have a great productivity tip, technique, or secret you'd like to share with the world. Is it one that you believe is rarely utilized or brand-spanking new?
I'd love to hear your thoughts and then promote the best ones. Unlike books, blogs should be focused conversations. This is your chance to contribute an entry to Productivity 101.
The best two ideas will both win and be explained on August 19th. Besides getting a day dedicated to your concept and a big kudos from me, you'll also receive a free Globe-Weis Everyday File ($20.00 value). This is a very good one-stop tickler system that I have recommended to others in the past. It has 42 folders (31 days, 12 months). Why is this not 43 folders? The last two days, 30 and 31, are combined into a single folder in this version. You can use this tickler to keep track of all kinds of papers, bills, concert tickets, birthday cards, etc. I'll ship one to each of the the winners, free of charge, anywhere in the world.
1) You may enter as many times as you like via email.
2) Be Honest and Creative (e.g. do not plagiarize from a book or website).


text:
Q: "I'm a Holmes' apprentice." Is this English correct?
This panel is from a popular Japanese manga "Detective Conan" (a.k.a. "Case Closed" in English-speaking nations).  The protagonist, Conan, shouts "I'm a Holmes' apprentice!!" (He wants to say how good his deduction skill is.)
Is this English correct?  If so, why is there "a" before "Holmes'"?  I learnt that you don't add a determiner before a genitive and that you say "one of my books" instead of "a my book".
So I suspect the English used in the manga is incorrect simply because the Japanese editor didn't know much about English grammar.  Am I right?

A: You're quite right: the English is wrong. He is either Holmes's apprentice (Holmes's only apprentice) or he is a Holmes apprentice (one among others).
Many people, including me, would say Holmes' isn't correct in any context. We say Holmes's house is on Baker Street, and we might say there are no Sherlock Holmeses nowadays, but Holmes' only exists in mistakes. But we argue about this regularly in English Language Learners.

A: This is bad grammar.
Possessive adjectives and nouns with possessive "'s" are definite nouns, just like nouns with "the" in front, so you can never put "a" in front of one. It's like saying "a the apprentice", which is clearly wrong.
One correct way of saying it would be reordering it to, "I am one of Holmes' apprentices!!"


They decided that Loki needed his own movie, where he popped up at key moments in history, being his chaotic self. Hardwick suggests that he should be The Doctor's companion, and with the TARDIS they can do just that. Because surely, these characters of Norse legend have a valid place in the world of Doctor Who. And the Rainbow Bridge is more sciencey anyway.
I just watched Silence in the Library, where The Doctor meets River Song for the first time. When flipping through her notebook, to see where they are on the timeline, she asks him if they've been to Asgard yet.
Sidenote: why is there no gif yet of Martin Starr from the Geography of Global Conflict episode of Community, saying "the math checks out" or whatever?! This is the perfect opportunity to use it!!!
Anyhow, I've decided I need to step away from it for a brief interlude. That is surely the first sign of an overdose.


This command is used to print out version information about OpenSSL.
all information, this is the same as setting all the other flags.
the date the current version of OpenSSL was built.
option information: various options set when the library was built.
The output of openssl version −a would typically be used when sending in a bug report.
The −d option was added in OpenSSL 0.9.7.


PGK1 terminator is a common terminator in yeast.
Before our test the whole system, we measured the strength of promoters which regulate the experssion of genes in our oscillator. As there is a natural ratio of the three proteins-KaiA, KaiB and KaiC in cyanobacteria. And a certain ratio of the three proteins has advantage of modeling.
We can draw a conclution about the strength of the three promoters. So we combine TEF1 promoter with KaiA and TEF1 terminator, PGK1 promoter with KaiB and PGK1 terminator and TDH3 promoter with AD-KaiC and ADH1 terminator. Similarly, we combina TEF1 promoter with CikA and TEF1 terminator, PGK1 promoter with RpaA and PGK1 terminator and TDH3 promoter with BD-SasA and ADH1 terminator. And here is only one combination of our experiment. To get more combinations, please see the part from BBa_K2637027 to BBa_K2637038.You can see more about our project to click here.