# On Empirical Risk Minimization with Dependent
and Heavy-Tailed Data

Abhishek Roy Department of Statistics, University of California,
<EMAIL_ADDRESS>Research of this author was supported in part by NSF
TRIPODS grant CCF-1934568 Krishnakumar Balasubramanian Department of
Statistics, University of California, Davis<EMAIL_ADDRESS>Research of
this author was supported in part by UC Davis CeDAR (Center for Data Science
and Artificial Intelligence Research) Innovative Data Science Seed Funding
Program. Murat A. Erdogdu Department of Computer Science and Department of
Statistical Sciences at the University of Toronto, and Vector Institute.
<EMAIL_ADDRESS>Research of this author was supported in part by NSERC
Grant [2019-06167], Connaught New Researcher Award, CIFAR AI Chairs program,
and CIFAR AI Catalyst grant

###### Abstract

In this work, we establish risk bounds for the Empirical Risk Minimization
(ERM) with both dependent and heavy-tailed data-generating processes. We do so
by extending the seminal works [Men15, Men18] on the analysis of ERM with
heavy-tailed but independent and identically distributed observations, to the
strictly stationary exponentially $\beta$-mixing case. Our analysis is based
on explicitly controlling the multiplier process arising from the interaction
between the noise and the function evaluations on inputs. It allows for the
interaction to be even polynomially heavy-tailed, which covers a significantly
large class of heavy-tailed models beyond what is analyzed in the learning
theory literature. We illustrate our results by deriving rates of convergence
for the high-dimensional linear regression problem with dependent and heavy-
tailed data.

##  1 Introduction

Given a random vector $(X,Y)\in\mathbb{R}^{d}\times\mathbb{R}$, with joint
distribution $(X,Y)\sim\pi$, and a class of closed, convex set of functions
${\cal F}\subset L_{2}(\pi)$, the objective in statistical learning theory is
to find the _best_ function in the set ${\cal F}$ that maps the input $X$ to
the target $Y$. The quality of this mapping is measured by a user-defined loss
function $\ell:\mathbb{R}\to\mathbb{R}^{+}\cup\\{0\\}$. The most well-studied
approach for the above task is that of _risk minimization_ , where the best
function is defined as the one that minimizes the expected loss over the set
${\cal F}$:

$\displaystyle f^{*}=\operatorname*{argmin}_{f\in{\cal
F}}P\ell_{f}\coloneqq\operatorname*{argmin}_{f\in{\cal
F}}\mathbb{E}_{\pi}\left[\ell\left(f(X)-Y\right)\right].$

The above problem requires the knowledge of the distribution $\pi$ which is
typically unknown in practice. However, we are usually given observations
$Z_{i}=(X_{i},Y_{i})$ for $i=1,\dots,N$, from the distribution $\pi$ which
leads to the _Empirical Risk Minimization_ (ERM) procedure defined as

$\displaystyle\hat{f}=\operatorname*{argmin}_{f\in{\cal
F}}P_{N}\ell_{f}\coloneqq\operatorname*{argmin}_{f\in{\cal
F}}\frac{1}{N}\sum_{i=1}^{N}\ell\left(f(X_{i})-Y_{i}\right).$

The convergence of the empirical risk minimizer $\hat{f}$ to the true risk
minimizer $f^{*}$ is typically analyzed by considering the underlying
empirical process, a topic which dates back to the seminal work of [VC71]; see
also [VDVW96, vdG00, BBM05, Kol06, Kol11]. In a representative analysis in
this setting, a majority of the works assume the observations $Z_{i}$ are
generated independent and identically distributed
($\operatorname*{\texttt{iid}}$) from $\pi$, and the analysis is based on
uniform concentration. However, there are important limitations associated
with this approach, particularly due to the (Talagrand’s) contraction
principle which naturally requires a Lipschitz loss function (see, for
example, [LT13, Corollary 3.17] or [Kol11, Theorem 2.3]). As a result, in
order to work with standard (unbounded) loss functions such as squared-error
loss or Huber loss, it is generally assumed that the range of $f\in{\cal F}$
is uniformly bounded and/or the noise $\xi\coloneqq Y-f(X)$ is also uniformly
bounded $\pi$-almost surely.

Several attempts have been made in the literature to overcome the limitations
of the standard ERM analysis. A significant progress was made by Mendelson
[Men15, Men18], who proposed the so-called _learning without concentration_
framework for analyzing ERM procedures with unbounded noise or loss functions.
The approach is based on a combination of small-ball type assumption on the
input samples $X_{i}$, along with developing multiplier empirical process
inequalities under weaker moment assumptions. We refer the interested reader,
for example, to [Men17b, Men17a, LM18, LRS15, GM20] for details. The
aforementioned works, while relaxing the prior analysis of ERM to handle
heavy-tailed data-generating process (DGP), still require the more stringent
$\operatorname*{\texttt{iid}}$ assumption for their analysis. This restricts
the practical applicability of the developed theoretical results
significantly. Indeed, heavy-tailed and dependent data appear naturally in
various practical learning scenarios [BF89, JM01, DKBR07]; however,
theoretical guarantees are still missing.

Our Contributions: Aiming to fill the above gap, we analyze ERM with convex
loss functions (that are locally strongly-convex around the origin) when the
DGP is both heavy-tailed and non-$\operatorname*{\texttt{iid}}$. We do so by
extending the small-ball technique of [Men15, Men18] to the strictly
stationary exponentially $\beta$-mixing data. In the
$\operatorname*{\texttt{iid}}$ case, the interaction between the noise and the
inputs is handled by an analysis based on multiplier empirical process.
However, developing similar techniques in the
non-$\operatorname*{\texttt{iid}}$ case is fundamentally restrictive due to
the limitations of the analysis based on empirical process. We side-step this
issue for the non-$\operatorname*{\texttt{iid}}$ case by directly making
assumptions on the interaction, which allows for it to be either exponentially
or polynomially heavy-tailed. For the exponentially heavy-tailed interactions,
we leverage the concentration inequalities developed by [MPR11]. For the
polynomially heavy-tailed case, we develop new concentration inequalities
extending the recent work [BMdlP20] to $\beta$-mixing random variables. We
illustrate our results in the context of ERM with sparse linear function class
and stationary $\beta$-mixing DGP under both squared and Huber loss.

Motivation: A natural question arises in this context: _Why study ERM with
convex loss functions when the DGP is heavy-tailed?_ Firstly, convex loss
functions cover a large class of robust loss function that are tailored to
deal with the heavy-tailed behavior present in the noise and/or input data.
Some examples include the Huber loss [Hub92], conditional value-at-risk [RU02,
RS06, MGW20, SY20] and the so-called spectral risk measures [Ace02, HH21].
While there exist studies for nonconvex loss functions suited for heavy-tailed
input data (for example, [Loh17]), such analyses are mostly in a model-based
setting and focus on estimation error. Secondly, while alternatives to ERM
have also been proposed and analyzed in the literature for the
$\operatorname*{\texttt{iid}}$ case (with the most prominent one being the
median-of-means framework and its variants [MM19, LM19, LL20, BM21]), it is
not immediately clear how to extend such methods to the dependent DGP that we
consider in this paper. We view our work as taking the first step in
developing risk bounds for statistical learning when the DGP is both heavy-
tailed and dependent.

Related Works: The seminal work [Yu94] extended the analysis based on
empirical process to the stationary mixing process using a blocking technique.
[Irl97] and [BR97] studied consistency of non-parametric regression methods
under mixing and exchangeability conditions on the DGP, respectively. [Nob99]
established lower bounds to achieving consistency when learning from dependent
data. [SHS09] studied consistency of ERM with $Z_{i}$ being an $\alpha$-mixing
(not necessarily stationary) process, when $\mathcal{F}$ is a reproducing
kernel Hilbert space. More recently, [Han21] and [DT20] studied learnability
under a general stochastic process setup. The works [AV90, BL97, Pes10, Gam03]
extend Valiant’s Probably Approximately Correct (PAC) learning model to
Markovian and related drifting DGP, assuming bounded loss function and/or
noise to obtain rates of convergence. Furthermore, [ZCY12] and [HS14] analyzed
ERM for least-squares regression (with bounded noise) with clipped loss
functions and an $\alpha$-mixing DGP. Rademacher complexity results for
predominantly stationary dependent processes were developed by [MS11] and
[MR08]. [RSS10] and [ALW13] developed PAC-Bayes bounds in the
non-$\operatorname*{\texttt{iid}}$ setting. [RST15, RS14] developed notions of
sequential Rademacher complexity to characterize the complexity in online
nonparametric learning in the worst-case. More recently [DDDJ19, KDD+21]
considered learning under weakly-dependent data for specific models. However,
such works mainly rely on bounded loss functions in their analysis.
Furthermore, [Mei00] and [AW12] studied model selection for time series
forecasting in a possibly unbounded setup. However their work does not
consider conditional prediction and is limited to light-tailed cases.

Apart from the aforementioned works, the recent works [KM17, HW19, WLT20] are
closely related to our setup as they consider rates of convergence of ERM
under heavy-tailed and dependent DGP. In [KM17, Section 8], generalization
bounds are developed when $Z_{i}$ is an asymptotically stationary
$\beta$-mixing sequence. However, their conditions on the function class
$\mathcal{F}$ are rather opaque and it is not clear if their method actually
handles the heavy-tailed DGP that we focus on. [HW19] considered a setup based
on a statistical model: for $i=1,\ldots,N$, $Y_{i}=f^{*}(X_{i})+\epsilon_{i}$,
with the following conditions: (i) $\epsilon_{i}$ being independent of
$X_{i}$, (ii) $X_{i}$ being independent of each other, and (iii)
$\epsilon_{i}$ being arbitrarily dependent. For this setting, they assumed
that the noise has a bounded $p$-th moment (with $p\geq 1$) and $\mathcal{F}$
satisfies the standard entropy condition (see, for example [Kol06, Example 4])
with exponent $\alpha\in(0,2)$ and obtained convergence rates of the order
$O(N^{-\frac{1}{2+\alpha}}+N^{-\frac{1}{2}+\frac{1}{2p}})$. Finally, [WLT20]
provides an analysis of $L_{1}$-regularized ERM with quadratic loss and linear
function class where the heavy-tailed behavior is induced by a sub-Weibull
assumption, and data dependency is characterized by a stationary
$\beta$-mixing condition. However, their analysis specializes to sparse linear
function classes and their focus is on parameter estimation error and in-
sample prediction accuracy.

##  2 Assumptions and Preliminaries

We assume that there exists a function $f^{*}\in{\cal F}$ that minimizes the
population risk ${\mathbb{E}}[\ell(f(X)-Y)]$. In what follows, we provide the
conditions that we require on the DGP, specifically, the exponentially
$\beta$-mixing condition, for characterizing the dependency among data points.

######  Definition 1 ([Yu94]).

Suppose that $\\{Z_{i}\\}_{i=-\infty}^{\infty}$ is a strictly stationary
sequence of random variables. For any
$i,j\in\mathbb{Z}\cup\\{-\infty,\infty\\}$, let $\sigma_{i}^{j}$ denote the
$\sigma$-algebra generated by $\\{Z_{b}\\}_{b=i}^{j}$. Then for any positive
integer $b$, the $\beta$-mixing coefficient of the stochastic process
$\\{Z_{i}\\}_{i=-\infty}^{\infty}$ is defined as

$\beta(b)=\sup_{n}\underset{B\in\sigma^{n}_{-\infty}}{\mathbb{E}}\big{[}\sup_{A\in\sigma_{n+b}^{\infty}}\left\lvert\mathbb{P}(A\>|\>B)-\mathbb{P}(A)\right\rvert\big{]}.$

The sequence $\\{Z_{i}\\}_{i=-\infty}^{\infty}$ is said to be $\beta$-mixing
if $\beta(b)\to 0$ as $b\to\infty$. Furthermore, it is said to be
exponentially $\beta$-mixing if there exist $\beta_{0},\beta_{1},r>0$ such
that $\beta(b)\leq\beta_{0}{\rm exp}(-\beta_{1}b^{r})$ for all $b$.

The $\beta$-mixing condition is frequently used when studying
non-$\operatorname*{\texttt{iid}}$ DGP, and imposes a dependence structure
between data samples that weakens over time. The coefficient $\beta(b)$ is a
measure of the dependence between events that occur within $b$ units in time.
Indeed, $\beta$-mixing is often used in the analysis of
non-$\operatorname*{\texttt{iid}}$ data in statistics and machine learning,
[Vid13]. Before stating our assumptions formally, we present the following
decomposition of empirical risk for a convex loss using Taylor’s expansion:

$\displaystyle
P_{N}\ell_{f}\geq\frac{1}{16N}\sum_{i=1}^{N}\ell^{\prime\prime}(\widetilde{\xi}_{i})(f-f^{*})^{2}(X_{i})+\frac{1}{N}\sum_{i=1}^{N}\ell^{\prime}(\xi_{i})(f-f^{*})(X_{i}),\vspace{-.05in}$
(1)

where $\widetilde{\xi}_{i}$ is a suitably chosen midpoint between
$f(X_{i})-Y_{i}$ and $f^{*}(X_{i})-Y_{i}\coloneqq\xi_{i}$. For quadratic loss
functions $\ell(t)=t^{2}$, $\ell^{\prime}(\xi_{i})=2\xi_{i}$ and
$\ell^{\prime\prime}(\widetilde{\xi}_{i})=2$, $\forall i$. At a high level,
establishing risk bounds boils down to proving a positive lower bound on the
second term on the Right Hand Side (RHS) of (1), and a concentration result
for the first term on the RHS with high probability. We now introduce the
precise assumptions we make on the DGP and the function class to formalize the
above strategy. For the sake of clearer exposition, we first introduce our
assumptions in the context of quadratic loss and then indicate the changes
required to handle more general locally strongly-convex loss functions.

######  Assumption 2.1 (Squared loss).

The DGP $\\{Z_{i}\\}_{i=-\infty}^{\infty}$ and the function class
$\mathcal{F}$ satisfy the following:

  1. (a)

$\beta$-mixing data. The process $\\{Z_{i}\\}_{i=-\infty}^{\infty}$ is a
strictly stationary exponentially $\beta$-mixing sequence, i.e.,
$\beta(k)\leq{\rm exp}(-ck^{\eta_{1}})$, for some $c,\eta_{1}>0$, with strict
stationary distribution $\pi$.

  2. (b)

Small ball condition. Let ${\cal F}\subset L_{2}(\pi)$ be closed, convex class
of functions and define ${\cal F}-{\cal F}\coloneqq\\{f-h:f,h\in{\cal F}\\}$.
Then, the function class $\mathcal{F}$ is such that there is a $\tau>0$ for
which $Q_{{\cal F}-{\cal F}}(2\tau)>0$, where $Q_{{\cal H}}(u)=\inf_{h\in{\cal
H}}{\mathbb{P}}\left(|h|\geq u\|h\|_{L_{2}}\right).$

  3. (c)

Deviations of interaction. The stationary noise $\xi_{1}$ and the error
$(f-f^{*})(X_{1})$ satisfy either:

    1. (i)

For all $f\in{\cal F}$, and $Z_{1}\sim\pi$, for some $\eta_{2}>0$ we have

$\displaystyle{\mathbb{P}}\left(|\xi_{1}(f-f^{*})(X_{1})-\mathbb{E}\left[\xi_{1}(f-f^{*})(X_{1})\right]|\geq
t\right)\leq{\rm exp}(1-t^{\eta_{2}}).$ (2)

or,

    2. (ii)

For all $f\in{\cal F}$, and $Z_{1}\sim\pi$, for some $\eta_{2}>2$, and $c>0$
we have

$\displaystyle{\mathbb{P}}\left(|\xi_{1}(f-f^{*})(X_{1})-\mathbb{E}\left[\xi_{1}(f-f^{*})(X_{1})\right]|\geq
t\right)\leq ct^{-\eta_{2}}.$ (3)

  4. (d)

Heavy-tail/data-mixing trade-off. Under condition (c)-(i), $1/\eta\coloneqq
1/\eta_{1}+1/\eta_{2}>1$.

Condition (a) above, exponentially $\beta$-mixing data, has been assumed in
various works, see for example [Vid13, WLT20, KM17], to obtain rates of
convergence for ERM procedures in general. Indeed, (exponential) mixing
assumption holds in several time-series applications. For example, [Mok88]
showed that certain ARMA processes can be modeled as an exponentially
$\beta$-mixing stochastic process. Furthermore [VK06] showed that globally
exponentially stable unforced dynamical systems subjected to finite-variance
continuous density input noise give rise to exponentially mixing stochastic
process; see also [FS12]. Condition (b), referred to as the well-known small-
ball condition, has been previously employed in the
$\operatorname*{\texttt{iid}}$ case [Men15]. Intuitively, it models _heavy-
tailedness_ by restricting the mass allowed near any small neighborhoods of
zero; thus, forcing the tails to be necessarily heavy. To our knowledge, the
small-ball condition has not been used under dependent DGP assumptions.
Condition (c) is proposed in this work as a way to model the interaction
between the stationary noise $\xi_{1}$ and the stationary error
$(f-f^{*})(X_{1})$. For the $\operatorname*{\texttt{iid}}$ setting, [Men15]
modeled the interaction between $\xi_{1}$ and $(f-f^{*})(X_{1})$ uniformly
over the class of $\mathcal{F}$ via the multiplier empirical process and
captured the complexity through a parameter $\alpha_{N}$ (see (108) for the
definition). This requires using symmetrization argument in the proof which is
not applicable in the non-$\operatorname*{\texttt{iid}}$ setting that we
consider in this work. In addition, how different tail conditions on the data
and noise affect the high-probability statement on the learning rate is not
apparent from the parameter $\alpha_{N}$. We revisit the relationship between
our condition (in the context of $\operatorname*{\texttt{iid}}$ observations)
and the multiplier empirical process approach used in [Men15] in Section F.
Finally, condition (d) models the relationship between the allowed degree of
dependency and the allowed degree of interaction between $\xi_{1}$ and
$(f-f^{*})(X_{1})$.

Next, we modify condition (c) in Assumption 2.1 for the case of general
locally strongly-convex loss functions because now the interaction part
involves $\ell^{\prime}(\xi)$ instead of $\xi$ (recall the decomposition (1)).

######  Assumption 2.2 (Convex loss).

When the loss function is locally strongly-convex around the origin and
globally convex, condition (c) in Assumption 2.1 is modified as:

  1. (c)

Deviations of interaction. The stationary noise $\xi_{1}$ and the error
$(f-f^{*})(X_{1})$ satisfy either,

    1. (i)

For all $f\in{\cal F}$, and $Z_{1}\sim\pi$, for some $\eta_{2}>0$ we have

$\displaystyle{\mathbb{P}}\left(|\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})-\mathbb{E}\left[\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right]|\geq
t\right)\leq{\rm exp}(1-t^{\eta_{2}}).$ (4)

or,

    2. (ii)

For all $f\in{\cal F}$, and $Z_{1}\sim\pi$, for some $\eta_{2}>2$, and $c>0$
we have

$\displaystyle{\mathbb{P}}\left(|\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})-\mathbb{E}\left[\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right]|\geq
t\right)\leq ct^{-\eta_{2}}.$ (5)

Complexity Measures: We now introduce the complexity measures that play a
crucial role in characterizing the rates of convergence. The use of
$\beta$-mixing assumption enables us to define complexity measures based on
the blocking technique proposed by [Yu94], also utilized by the works of
[MR08, KM17, WLT20]. We partition the training sample of size $N$,
$S\coloneqq\\{Z_{i}\\}_{i=1}^{N}$, into two sequences of blocks $S_{a}$ and
$S_{b}$. Each block in $S_{a}$, and $S_{b}$ is of length $a$, and $b$
respectively. $S_{a}$ and $S_{b}$, both are of length $\mu$, i.e.,
$\mu(a+b)=N$. Formally, $S_{a}$ and $S_{b}$ are given by

$\textstyle
S_{a}=\left(Z_{1}^{(a)},Z_{2}^{(a)},\cdots,Z_{\mu}^{(a)}\right)\quad\text{with
}Z_{i}^{(a)}=\\{z_{(i-1)(a+b)+1},\cdots,z_{(i-1)(a+b)+a}\\},$ $\textstyle
S_{b}=\left(Z_{1}^{(b)},Z_{2}^{(b)},\cdots,Z_{\mu}^{(b)}\right)\quad\text{~{}with
}Z_{i}^{(b)}=\\{z_{(i-1)(a+b)+a+1},\cdots,z_{(i-1)(a+b)+a+b}\\}.$ (6)

Based on this blocking technique, we require the following definition of
Rademacher complexity.

######  Definition 2.

Let $\\{\widetilde{X}_{i}\\}_{i=1}^{\mu}$ be an $\operatorname*{\texttt{iid}}$
sample from the strict stationary distribution $\pi$. Let $\mathcal{D}$ be the
unit-$L_{2}(\pi)$ ball centered at $f^{*}$. For every $\gamma>0$, define

$\displaystyle\omega_{\mu}(\mathcal{F}-\mathcal{F},\gamma)\coloneqq\inf\left\\{r>0:\mathbb{E}\left[\sup_{h\in(\mathcal{F}-\mathcal{F})~{}\cap~{}r\mathcal{D}}\left\lvert\frac{1}{\mu}\sum_{i=1}^{\mu}\epsilon_{i}h(\widetilde{X}_{i})\right\rvert\right]\leq\gamma
r\right\\},\vspace{-.02in}$ (7)

where $\\{\epsilon_{i}\\}_{i=1}^{\mu}$ are $\operatorname*{\texttt{iid}}$
Rademacher variables taking values $\pm 1$ with probability $1/2$.

The quantity $\omega_{\mu}({\cal H},\gamma)$ provides a localized complexity
measure for the function class $\mathcal{F}$, and serves as a generalization
of the standard Rademacher complexity in the
non-$\operatorname*{\texttt{iid}}$ setting. For the case of locally strongly-
convex losses, we need the following related measures of complexity.

######  Definition 3.

For a function class ${\cal H}\\!\subset\\!L_{2}(\pi)$, a sample of size $N$
from a strictly stationary $\beta$-mixing sequence with stationary
distribution $\pi$ satisfying Assumption 2.1-(a), and $\zeta_{1},\zeta_{2}>0$,
we define:

$\displaystyle\omega_{1}({\cal H},N,\zeta_{1})$
$\displaystyle=\inf\left\\{r>0:\mathbb{E}\left[\|G\|_{{\cal H}\cap
rD}\right]\leq\zeta_{1}rN^{\frac{\eta_{1}}{2(1+\eta_{1})}}\right\\}~{}~{}\text{and}~{}~{}\omega_{2}({\cal
H},\mu,\zeta_{2})=\omega_{\mu}(\mathcal{H},\zeta_{2}),$

where $\mu=N^{\frac{\eta_{1}}{(1+\eta_{1})}}$, $\|G\|_{{\cal
H}}=\sup_{h\in{\cal H}}G_{h}$, and $\\{G_{h}:h\in{\cal H}\\}$ is the canonical
Gaussian process indexed by ${\cal H}$ with a covariance induced by
$L_{2}(\pi)$. Moreover, we let

$\omega_{Q}({\cal F}-{\cal
F},N,\zeta_{1},\zeta_{2})\coloneqq\max(\omega_{1}({\cal
H},N,\zeta_{1}),\omega_{2}({\cal H},\mu,\zeta_{2})).$

Note that in Definitions 2 and 3, the scaling is in terms of number of blocks
$\mu$ instead of $N$. The number of blocks $\mu$ can be thought of as the
effective sample size under dependency, and as $\eta_{1}\to\infty$, one has
$\mu\to N$. The term $\mathbb{E}\left[\|G\|_{{\cal H}\cap rD}\right]$
appearing in Definition 3 is termed as the localized Gaussian width and is
also a widely used complexity measure in the literature. Note that while in
the case of quadratic loss function, the bound is in terms of local
Rademacher-based complexity measure, whereas in the convex case, we require
both Gaussian and Rademacher-based complexity measures to establish the bound,
mostly due to technical reasons in the proof. An intuitive explanation for
this has eluded us thus far; see also [Men18, Lemma 4.2].

Concentration Inequalities for Heavy-tails: We now restate [MPR11, Theorem 1],
in a form adapted to our setting below. This result is required to handle
interactions of noise and input that satisfy condition (c)-(i) of Assumption
2.1. It is straightforward to check that the conditions required by [MPR11]
are immediately satisfied under our Assumption 2.1. Indeed, while the results
in [MPR11] are stated for $\tau$-mixing sequences, condition (a) in Assumption
2.1 implies that the process $\\{Z_{i}\\}_{i=-\infty}^{\infty}$ is
exponentially $\tau$-mixing [CG14], i.e., for a constant $c^{\prime}>0$,
$\tau(k)\leq e^{-c^{\prime}k^{\eta_{1}}}$.

######  Lemma 2.1 ([MPR11]).

Let $\\{W_{j}\\}_{j\geq 1}$ be a sequence of zero-mean real-valued random
variables satisfying conditions (a), (c)-(i), and (d) of Assumption 2.1.
Define $\varkappa_{M}(x)=(x\wedge M)\vee(-M)$, for some $M$, where $(x\wedge
y)=\min(x,y)$, and $(x\vee y)=\max(x,y)$, and set,

$\displaystyle V\coloneqq\sup_{M\geq
1}\sup_{i>0}\Big{(}\textsc{var}(\varkappa_{M}(W_{i}))+2\sum_{j>i}\left\lvert\textsc{cov}\left(\varkappa_{M}(W_{i}),\varkappa_{M}(W_{j})\right)\right\rvert\Big{)}.$
(8)

Note that $V$ is finite. Then, for any $N\geq 4$, there exist positive
constants $C_{1},C_{2},C_{3}$, and $C_{4}$ depending only on
$c,\eta_{1},\eta_{2}$ such that, for any $t>0$, we have

$\displaystyle{\mathbb{P}}\left(\sup_{j\leq
N}\left\lvert\sum_{i=1}^{j}W_{i}\right\rvert\geq t\right)\leq
Ne^{-\frac{t^{\eta}}{C_{1}}}+e^{-\frac{t^{2}}{C_{2}NV}}+e^{-\frac{t^{2}}{C_{3}N}{\rm
exp}\left(\frac{t^{\eta(1-\eta)}}{C_{4}(\log t)^{\eta}}\right)}.$ (9)

To deal with polynomially tailed interactions, i.e., under condition (c)-(ii)
of Assumption 2.1, we prove a concentration inequality for the sum of
exponentially $\beta$-mixing random variables with polynomially heavy-tails,
which may be of independent interest.

######  Lemma 2.2 (Concentration for heavy-tailed $\beta$-mixing sum).

Let $\\{W_{j}\\}_{j\geq 1}$ be a sequence of zero-mean real valued random
variables satisfying conditions (a) and (c)-(ii) of Assumption 2.1, for some
$\eta_{2}>2$. Then for any positive integer $N$, $0\leq d_{1}\leq 1$, and
$d_{2}\geq 0$, and for any $t>1$, we have,

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i=1}^{j}W_{i}\right\rvert\geq t\right)\leq$
$\displaystyle\frac{2^{\eta_{2}+3}}{(d_{2}\log
t)^{\frac{1-\eta_{2}}{\eta_{1}}}}\frac{N}{t^{(1+d_{1}(\eta_{2}-1))}}+8\frac{N}{t^{(1+c^{\prime}d_{2})}}+2e^{-\frac{t^{2-2d_{1}}(d_{2}\log
t)^{1/\eta_{1}}}{9N}},$ (10)

where $c^{\prime}>0$ is a constant.

Note that we do not need condition (d) of Assumption 2.1 for Lemma 2.2. Since
the tail probabilities decay polynomially and the mixing coefficients decay
exponentially fast, the effect of heavy-tail dominates and hence, there is no
trade-off between $\eta_{1}$ and $\eta_{2}$. Lemma 2.2 extends the results of
[BMdlP20] (on $\operatorname*{\texttt{iid}}$ heavy-tailed random variables) to
the exponentially $\beta$-mixing setting. The results of [BMdlP20] show that
even for the $\operatorname*{\texttt{iid}}$ case, the tail probability of the
sum decays polynomially with $t$. We show that similar polynomial tail bounds
can be obtained (up to $\log$ factors) even in the dependent setting.
Furthermore, when $\beta(k)=0,k>0$, the sequence is
$\operatorname*{\texttt{iid}}$, in which case we recover the result of
[BMdlP20]. We also remark that the above two results are crucial to derive our
convergence rates for ERM. As a preview, when the DGP has only
$(2+\delta)$-moments, for some $\delta>0$, Lemma 2.2 eventually will lead to
risk bounds that hold with polynomial probability, whereas when the DGP is
sub-Weibull (see Definition 4), Lemma 2.1 would lead to risk bounds that hold
with exponential probability.

##  3 Main Results

In this section, we state our main results on the rates of convergence of ERM
for both squared and convex loss functions. First, we consider the squared
loss.

######  Theorem 3.1 (Rates of ERM with squared loss).

Consider the ERM procedure with the squared error loss. For
$\tau_{0}<\tau^{2}Q_{\cal H}(2\tau)/8$, setting $\mu={N^{r}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}/{4}$, for some constants $c,c^{\prime}>0$,
and $0<r<1$, we have, for sufficiently large $N$, and some positive constants
$\widetilde{C}_{1},\widetilde{C}_{2}$, the following:

  1. 1.

Under conditions (a), (b), (c)-(i), and (d) of Assumption 2.1, for $\
0<\iota<1/4$,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\coloneqq\left(\int(\hat{f}-f^{*})^{2}d\pi\right)^{\frac{1}{2}}\leq\max\left\\{N^{-\frac{1}{4}+\iota},\omega_{\mu}\left({\cal
F}-{\cal F},\frac{\tau Q_{{\cal F}-{\cal F}}(2\tau)}{16}\right)\right\\},$
(11)

with probability at least (for $V$ as defined in (8))

$\displaystyle 1-\widetilde{C}_{1}N^{r}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}{\rm
exp}(-N^{(1-r)\eta_{1}})-\widetilde{C}_{2}N{\rm
exp}\left(-(N^{\frac{1}{2}+2\iota}\tau_{0})^{\eta}\right).$ (12)

  2. 2.

Under conditions (a), (b), and (c)-(ii) of Assumption 2.1, for $\
0<\iota<(1-1/\eta_{2})/4$,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{1}{4}\left(1-\frac{1}{\eta_{2}}\right)+\iota},\omega_{\mu}\left({\cal
F}-{\cal F},\frac{\tau Q_{{\cal F}-{\cal F}}(2\tau)}{16}\right)\right\\}.$
(13)

with probability at least

$\displaystyle 1-\widetilde{C}_{1}N^{r}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}{\rm
exp}(-N^{(1-r)\eta_{1}})-\widetilde{C}_{2}\tau_{0}^{-\frac{2\eta_{2}}{1+\eta_{2}}}N^{-\frac{4\iota\eta_{2}}{1+\eta_{2}}}.$
(14)

The detailed expression of the probabilities are provided in the Appendix
(Theorem B.1).

######  Remark 1.

To the best of our knowledge, the above result is the first result on
understanding rates of convergence of ERM with squared error loss functions
with unbounded noise (as well as the loss) for heavy-tailed dependent data.
For a wide range of function classes $\mathcal{F}$ used in practice (see
Section 4), the dominant term in the rate of convergence is
$N^{-\frac{1}{4}+\iota}$, for $0<\iota<1/4$. Furthermore, under the stronger
condition (c)-(i) of Assumption 2.1, the risk bound holds with exponential
probability, whereas under the weaker condition (c)-(ii), it holds only with
polynomial probability.

We now show that when the small-ball condition in Assumption 2.1 is replaced
with the stronger norm-equivalence assumption, also considered in [MZ20], one
could obtain improved rates. Examples of random vectors that satisfy the norm-
equivalence conditions include multivariate student $t$-distribution and sub-
exponential random variables. We refer to Section 4 for illustrative examples.

######  Assumption 3.1 ($L_{p}-L_{2}$ norm-equivalence).

Let ${\cal F}\subset L_{q}(\pi)$ be a class of functions for some $q\geq 3$.
The function class ${\cal F}-{\cal F}=\\{f-h:f,h\in{\cal F}\\}$ is
$L_{p}-L_{2}$ norm-equivalent for some $p>2$, if there exists an $M_{1}>0$
such that, $\|h\|_{L_{p}}\coloneqq(\int|h|^{p}\,d\pi)^{1/p}\leq
M_{1}\|h\|_{L_{2}},~{}\forall h\in{\cal F}-{\cal F}$.

######  Corollary 3.1.

For the ERM procedure with squared error loss, under Assumptions 2.1, with
condition (b) replaced by Assumption 3.1 with $p=8$, for some
$0<\iota<\frac{1}{2}$ and $r,\mu$ and $\tau_{0}$ same as in Theorem 3.1, for
sufficiently large $N$, we have

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{1}{2}+\iota},\omega_{\mu}({\cal
F}-{\cal F},\tau Q_{{\cal F}-{\cal F}}(2\tau)/16)\right\\},$ (15)

with probability at least (for some constants $\widetilde{C}_{1}$ and
$\widetilde{C}_{2}$)

$\displaystyle 1-\widetilde{C}_{1}N^{r}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}{\rm
exp}(-N^{(1-r)\eta_{1}})-\widetilde{C}_{2}N{\rm
exp}\left(-(N^{2\iota}\tau_{0})^{\eta}/M_{1}\right).$

######  Remark 2.

In the model-based nonparametric regression setting (as discussed in Related
Works) with $X_{i}$ being independent of $\xi_{i}$ for all $i=1,\ldots,n$, but
$\xi_{i}$ being dependent on each other, in [HW19, Proposition 3] authors show
a lower bound of $N^{-\frac{1}{2+\epsilon}}$ for some $\epsilon>0$, for
sufficiently heavy-tailed input $X_{i}$. The above result provides an upper
bound of similar order, for a more general setting in comparison to [HW19]. We
also remark that for Corollary 3.1, in the model-based setting, if we assume
that $\xi_{i}$ is independent of $X_{i}$, we have the same conclusion with
just $p=4$ instead of $p=8$. Furthermore, note that in part 2 of Theorem 3.1,
$L_{8}$ norm does not exist for $\eta_{2}\leq 8$. We have elaborated more on
how this result compares Theorem 3.1 in [Men15] later in Section F.

We now present our results for the class of convex loss functions that are
locally strongly-convex.

######  Assumption 3.2 (Convex loss).

The loss function $\ell:\mathbb{R}\to\mathbb{R}^{+}\cup\\{0\\}$ is a convex
loss function which is strongly convex in the neighborhood of $0$, i.e., there
exists a $t_{2}>0$ such that for any $x,y\in[-t_{2},t_{2}]$,
$\ell(y)\geq\ell(x)+\ell(x)^{\prime}(y-x)+\mu_{c}(y-x)^{2}/2$ for some
constant $\mu_{c}>0$.

######  Theorem 3.2 (Rates of ERM with convex loss).

Consider ERM with loss functions that satisfy Assumption 3.2. For
$\tau_{0}<c_{2}Q_{{\cal F}-{\cal F}}(2\tau)\rho(0,t_{2})\tau^{2}$,
$t_{2}=\mathcal{O}((\kappa_{0}+1/\sqrt{Q_{{\cal H}}(2\tau)})\|\xi\|_{L_{2}})$,
setting $\mu=N^{\eta_{1}/(1+\eta_{1})}$, for some constants $c,c^{\prime}>0$,
we have, for any $N\geq 4$, the following:

  1. 1.

Under conditions (a), (b), (c)-(i), and (d) of Assumption 2.1, for $\
0<\iota<\frac{1}{4}$,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{1}{4}+\iota},2\omega_{Q}({\cal
F}-{\cal F},N,\zeta_{1},\zeta_{2})\right\\},$ (16)

with probability at least (for $V$ is defined in (8) and some positive
$c_{9},c_{10},\widetilde{C}_{3}$)

$\displaystyle 1-c_{9}Q_{{\cal
H}}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{10}Q_{{\cal
H}}(2\tau)^{1+\frac{1}{\eta_{1}}}N^{\frac{\eta_{1}}{1+\eta_{1}}}}-\widetilde{C}_{3}N{\rm
exp}\left(-(N^{\frac{1}{2}+2\iota}\tau_{0})^{\eta}/C_{1}\right).$

  2. 2.

Under conditions (a), (b), and (c)-(ii) of Assumption 2.1, for $\
0<\iota<(1-1/\eta_{2})/4$,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{(1-1/\eta_{2})}{4}+\iota},2\omega_{Q}({\cal
F}-{\cal F},N,\zeta_{1},\zeta_{2})\right\\},$ (17)

with probability at least (for constants $c_{9},c_{10},\widetilde{C}_{4}>0$)

$\displaystyle 1-c_{9}Q_{{\cal
H}}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{10}Q_{{\cal
H}}(2\tau)^{1+\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}}-\widetilde{C}_{4}\tau_{0}^{-\frac{2\eta_{2}}{1+\eta_{2}}}N^{-\frac{4\iota\eta_{2}}{1+\eta_{2}}}.$
(18)

To the best of our knowledge, the above result is the first result on
understanding rates of convergence of ERM with convex loss functions with
unbounded noise (as well as the loss) for heavy-tailed dependent data. The
above result highlights the advantage of using a robust loss function, e.g.
Huber loss, over a quadratic loss function. For example, if $(f-f^{*})(X)$ has
a sub-Weibull tail and the noise $\xi$ has polynomial tail, one can still
obtain risk bounds with exponential probability. This is because in this case
$\ell^{\prime}(\xi)(f-f^{*})(X)$ can still be sub-Weibull for a suitable
chosen $\ell^{\prime}(\xi)$. Such a situation arises, for example, when there
are outliers even if the data is light-tailed. With a squared error loss, one
won’t be able to obtain a risk bound with exponential probability in this
scenario. We will illustrate this in Section 4.3 through Huber loss, a popular
choice of robust loss function in robust statistics. Similar to the quadratic
case, we also have an improved result when the small-ball condition is
replaced with the norm-equivalence condition. Due to space constraints, we
state and prove it in the Appendix B.2.

##  4 Illustrative Examples

We illustrate the results of Section 3 with three examples, based on sub-
Weibull random variables and Pareto random variables, that are canonical
models of heavy-tailed data in the literature.

###  4.1 Example 1:$\beta$-mixing Sub-Weibull DGP with Squared Error Loss

Here, we consider sub-Weibull random variables to model the heavy-tailed
behavior in the DGP.

######  Definition 4 (Sub-Weibull random vectors).

A real-valued random variable $X$ is said to be sub-Weibull with parameter
$\eta>0$, if there are constants $K_{1},K_{2}>0$, such that we have
$\mathbb{P}\left(|X|>t\right)\leq 2{\rm
exp}\left(-(t/K_{1})^{\eta}\right),~{}\text{or
equivalently}~{}~{}\|X\|_{p}=\mathbb{E}\left[|X|^{p}\right]^{1/p}\leq
K_{2}p^{\frac{1}{\eta}}.$ Based on this, a random vector $X\in\mathbb{R}^{d}$
is said to be marginally sub-Weibull with parameter $\eta>0$ if each
coordinate of $X$ is sub-Weibull with $\eta$. We use $X\sim\textsc{sw}(\eta)$
to represent this fact.

The above family of distributions define a rich class of random variables,
allowing for heavier tails than sub-Gaussian tails ($\eta=2$) or sub-
exponential tails ($\eta=1$). Let $\\{\delta_{i}\\}_{i\in\mathbb{Z^{+}}}$ be
an $\operatorname*{\texttt{iid}}$ sequence of $d$-dimensional random vectors
with independent coordinates with $\delta_{i}\sim\textsc{sw}(\eta_{\delta})$.
Assume that the dependent input vectors are generated according to the model

$\displaystyle X_{i}=AX_{i-1}+\delta_{i},$ (19)

where $A\in\mathbb{R}^{d\times d}$ with spectral radius less than $1$. For
simplicity, let $A=\sigma_{0}^{2}I_{d}$ where $\sigma_{0}^{2}<1$, and
$\\{Y_{i}\\}_{i\in\mathbb{Z^{+}}}$ be a univariate response sequence given by
$Y_{i}={\theta^{*}}^{\top}X_{i}+\xi_{i}$, where $\theta^{*}\in B_{1}^{d}(R)$
belongs to the $\ell_{1}$-norm ball in $\mathbb{R}^{d}$ with the radius $R$,
and $\\{\xi_{i}\\}_{i=1}^{n}$ is an i.i.d sequence independent of $X_{i}$
$\forall i$, and $\xi_{i}\sim\textsc{sw}(\eta_{\xi})$ for $0<\eta_{\xi}<1$ has
independent coordinates. To proceed with learning framework, we consider ERM
with squared loss and the function class $\mathcal{F}\coloneqq{\cal
F}_{R}=\left\\{\langle\theta,\cdot\rangle:\theta\in B_{1}^{d}(R)\right\\}$. We
denote the difference function class ${\cal F}_{R}-{\cal F}_{R}$ by ${\cal
H}_{R}$. We show that conditions (a), (b), (c), and (d) of Assumption 2.1, and
Assumption 3.1 are satisfied, in the following section.

####  4.1.1 Verification of Assumption 2.1 for Example 4.1

[WZLL20] showed that the time series given by (19) is stable, strict sense
stationary, with $X_{i}\sim\textsc{sw}(\eta_{X})$, for some $1>\eta_{X}>0$. As
shown in [WLT20], $\\{(X_{i},Y_{i})\\}$ is a strictly stationary sequence;
thus, we obtain that is also a $\beta$-mixing sequence with exponentially
decaying coefficients as in condition (a) of Assumption 2.1. Now we verify the
small-ball condition (b) of Assumption 2.1. Let, for any
$\theta=(\theta_{1},\cdots,\theta_{d})\neq 0$, $d_{1}$ denote the set of non-
zero coordinates of $\theta$. W.l.o.g lets assume $T={1,2,\cdots,d_{1}}$. Let
$\mathbb{E}\left[X_{i}^{2}\right]=\sigma_{i}^{2}$ and $\sigma_{0}=\min_{1\leq
i\leq{d_{1}}}\sigma_{i}$. Then
$\mathbb{E}\left[\left(\theta^{\top}X\right)^{2}\right]=\sum_{i=1}^{d_{1}}\theta_{i}^{2}\sigma_{i}^{2}\geq\sigma_{0}^{2}\|\theta\|_{2}^{2}.$
Since $X_{i}\sim SW(\eta_{X})$, we have $\|\theta_{i}X_{i}\|_{8}\leq
K_{1}|\theta_{i}|8^{\eta_{X}}.$ So,

$\displaystyle\|\theta^{\top}X\|_{8}\leq
K_{1}\|\theta\|_{1}8^{\eta_{X}}\leq\frac{K_{1}\|\theta\|_{1}8^{\eta_{X}}}{\sigma_{0}\|\theta\|_{2}}\|\theta^{\top}X\|_{2}\leq\frac{K_{1}\sqrt{d_{1}}8^{\eta_{X}}}{\sigma_{0}}\|\theta^{\top}X\|_{2}.$
(20)

Then using Lemma 4.1 of [Men15], for any $0<u<1$, we have
${\mathbb{P}}\left(\left\lvert\theta^{\top}X\right\rvert\geq
u\|\theta^{\top}X\|_{L_{2}}\right)\geq\left((1-u^{2})/(K_{1}^{2}8^{2/\eta_{X}+1})\right)^{4/3}.$
So condition (b) of Assumption 2.1 is true here. This also implies that
Assumption 3.1 is true in this case for $p=8$. As an immediate consequence of
[VGNA20, Proposition 2.3], we have that condition (c)-(i) in Assumption 2.1 is
valid here with $\eta_{2}=\max(\eta_{X},\eta_{\xi})<1$. Since $1/\eta_{2}>1$,
condition (d) holds true.

######  Proposition 4.1.

Consider the learning problem described above. Then with probability at least

$\displaystyle 1-\widetilde{C}_{1}N^{r}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}{\rm
exp}(-N^{(1-r)\eta_{1}})-\widetilde{C}_{2}N{\rm
exp}\left(-(N^{2\iota}\tau_{0})^{\eta}/M_{1}\right),$

we have

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{\frac{2c_{3}R\log(ed)^{\frac{1}{\eta}}}{\sqrt{Q_{\cal
H}(2\tau)}c^{\frac{1}{2\eta_{1}}}}N^{-\frac{1}{2}+\iota},N^{-\frac{1}{2}+\iota}\right\\}.$

The proof of Proposition 4.1 could be found in the Appendix C.2.

######  Remark 3.

In a related setting (i.e., assuming $\theta^{*}$ is exactly $s$-sparse)
[WLT20, Corollary 9] presents parameter estimation error which is of the same
order as $\|\hat{f}-f^{*}\|_{L_{2}}$ (indeed, for simplicity $R$ could be
thought of being at the same order as $s$) since we assume $X$ has finite
variance. So with slightly better probability guarantee, we recover the same
rate ($\iota$ can be arbitrarily close to 0) as [WLT20, Corollary 9] in the
above proposition.

###  4.2 Example 2: $\beta$-mixing Pareto DGP with Squared Error Loss

Let $\widetilde{X}_{t,i}$ denote the $i$-th coordinate of the vector
$\widetilde{X}_{t}\in\mathbb{R}^{d}$. We consider the process given in
[Pil91]: For $i=1,2,\cdots,d$, $\eta_{3}>2+2\iota$, where $\iota>0$ is a small
number, and $t=0,1,\cdots$, define

$\widetilde{X}_{t,i}=\begin{cases}2^{\frac{1}{\eta_{3}}}\widetilde{X}_{t-1,i}&\quad\text{with
probability }1/2\\\
\min\left(2^{\frac{1}{\eta_{3}}}\widetilde{X}_{t-1,i},\delta_{t,i}\right)&\quad\text{with
probability }1/2\end{cases}$

where $\\{\delta_{t,i}\\}_{i=1,2,\cdots,d,t=1,2,\cdots}$ is a sequence of
$\operatorname*{\texttt{iid}}$ Pareto random variables with the distribution
$L_{+}(\delta;\eta_{3},d_{i})=\eta_{3}(d_{i}\delta)^{\eta_{3}-1}/\left(1+(d_{i}\delta)^{\eta_{3}}\right)^{2}$
for $\delta>0,\eta_{3}>2+2\iota$, and we write $X\sim L_{+}(\eta,\sigma)$ to
denote that $X$ is a Pareto random variable with parameters $\eta$ and
$\sigma$. The survival function of $\delta\sim L_{+}(\eta_{3},d)$ is given by,
$\mathbb{P}(\delta>t)=(1+(dt)^{\eta_{3}})^{-1}$, for $t>0$. Let
$\widetilde{X}_{1,t}$ and $\widetilde{X}_{2,t}$ be two independent trails of
the process in (4.2). Let $\\{U_{t}\\}_{t=0,1,\cdots}$ be a sequence of
$\operatorname*{\texttt{iid}}$ $U[0,1]$ random variables. Now consider the
process ${X}_{t,i}=\widetilde{X}_{1,t,i}\mathbbm{1}(U_{t}\leq
1/2)-\widetilde{X}_{2,t,i}\mathbbm{1}(U_{t}>1/2)$. The marginal distribution
of $X_{t,i}$ is given by symmetric Pareto distribution, i.e.,

$\displaystyle
L(x;\eta_{3},d_{i})=\frac{\eta_{3}(d_{i}|\delta|)^{\eta_{3}-1}}{2\left(1+(d_{i}|\delta|)^{\eta_{3}}\right)^{2}}\quad-\infty<\delta<\infty,\eta_{3}>2+2\iota.$
(22)

Now, let $\\{Y_{i}\\}_{i\in\mathbb{Z^{+}}}$ be a sequence given by
$Y_{i}={\theta^{*}}^{\top}X_{i}+\upsilon_{i}$, where $\theta^{*}\in
B_{1}^{d}(R)$, as before. Let $\\{\upsilon_{i}\\}_{i=1}^{n}$ be an
$\operatorname*{\texttt{iid}}$ sequence of $0$ mean random variables
independent of $X_{i}$ for all $i$, with heavy tails such that for all $t>0$,
$\mathbb{P}\left(|\upsilon_{i}|\geq t\right)\leq 1/(1+t^{\eta_{4}})$,
$\eta_{4}>2+2\iota$. Like in Example 4.1, we consider ERM with squared loss
and the function class $\mathcal{F}\coloneqq{\cal
F}_{R}=\left\\{\langle\theta,\cdot\rangle:\theta\in B_{1}^{d}(R)\right\\}$,
where $B_{1}^{d}(R)$ denotes the $d$-dimensional $\ell_{1}$-ball with radius
$R$. We denote the difference function class ${\cal F}_{R}-{\cal F}_{R}$ by
${\cal H}_{R}$. We show that conditions (a), (b), and (3)-(ii) of Assumption
2.1 hold here in the following section.

####  4.2.1 Verification of Assumption 2.1 for Example 4.2

[Pil91] shows that the AR(1) process given by (4.2) is strictly stationary if
$\tilde{X}_{0,i}\sim L_{+}(\eta_{3},d_{i})$, and $\tilde{X}_{0,i}$ are
independent of each other for $i=1,2,\cdots,d$. The stationary distribution is
given by $L_{+}(\eta_{3},d_{i})$. Let
$\pi(X_{t_{1}},X_{t_{2}},\cdots,X_{t_{n}})$ be the joint distribution of
$X_{t_{1}},X_{t_{2}},\cdots,X_{t_{n}}$ for a set of time points
$t_{1},t_{2},\cdots,t_{n}$. Now for any positive integer $k$,

$\displaystyle\pi(\\{X_{t_{i}+k}\\}_{i=1}^{n})=\pi(\\{\tilde{X}_{1,t_{i}+k}\mathbbm{1}(U_{t_{i}+k}\leq
1/2)-\tilde{X}_{2,t_{i}+k}\mathbbm{1}(U_{t_{i}+k}>1/2)\\}_{i=1}^{n})$
$\displaystyle=$
$\displaystyle\pi(\\{\tilde{X}_{1,t_{i}}\mathbbm{1}(U_{t_{i}}\leq
1/2)-\tilde{X}_{2,t_{i}}\mathbbm{1}(U_{t_{i}}>1/2)\\}_{i=1}^{n})=\pi(\\{X_{t_{i}}\\}_{i=1}^{n}).$
(23)

The second equality above follows from the fact $\tilde{X}_{1,t}$ and
$\tilde{X}_{2,t}$ are strictly stationary process and $\\{U_{t}\\}$ is
$\operatorname*{\texttt{iid}}$. So $X_{t}$ is a strictly stationary process
with marginal distribution of $X_{t,i}$ given by symmetric Pareto distribution

$\displaystyle
L(x;\eta_{3},d_{i})=\frac{\eta_{3}(d_{i}|\delta|)^{\eta_{3}-1}}{2\left(1+(d_{i}|\delta|)^{\eta_{3}}\right)^{2}}\quad-\infty<\delta<\infty,\eta_{3}>2+2\iota.$
(24)

Without loss of generality we will assume that $d_{1}\leq d_{2}\leq\cdots\leq
d_{d}$, $\sum_{i=1}^{d}1/d_{i}=K_{0}$, and $d_{1}\geq C_{6}^{\prime}$ for some
constants $K_{0},C_{6}^{\prime}>0$. It is shown in Lemma 1 of [Ris08], that
the AR(1) process in (4.2) is $\phi$-mixing with $\phi(k)=k\log 2/(2^{k}-1)$,
$k=1,2,\cdots$. where $\phi$-mixing coefficients are defined as in [Bra05]. We
also have $\beta(k)\leq\phi(k)\leq k\log 2/(2^{k}-1)\leq e^{-k/3}.$ Since
$X_{t}$ depends only on $X_{1,t}$, $X_{2,t}$, and $U_{t}$, $X_{1,t}$, and
$X_{2,t}$ are independent and exponentially $\beta$-mixing, and $U_{t}$ is
$\operatorname*{\texttt{iid}}$, $X_{t}$ is also exponentially $\beta$-mixing.

  * •

Since $Y_{i}$ depends only on $X_{i}$, and $\upsilon_{i}$ are
$\operatorname*{\texttt{iid}}$, $\\{(X_{i},Y_{i})\\}$ is a strictly stationary
$\beta$-mixing sequence with $\beta(k)\leq e^{-k/3}$. So condition (a) of
Assumption 2.1 is true here.

  * •

Now we will verify condition (b) of Assumption 2.1. Let $\sigma_{X,p}$ denote
$\|X\|_{p}$ for $p>0$. Then

$\displaystyle\mathbb{E}\left[\left(\theta^{\top}X\right)^{2}\right]=\sum_{i=1}^{d}\frac{\theta_{i}^{2}\sigma_{X_{i},2}^{2}}{d_{i}^{2}}\geq\sigma_{0}^{2}\sum_{i=1}^{d}\frac{\theta_{i}^{2}}{d_{i}^{2}},$
(25)

where $\sigma_{0}=\min_{i}\sigma_{X_{i},2}$, $i=1,2,\cdots,d$. Since
$X_{i}\sim L(\eta_{3})$, for any $\theta_{i}\in\mathbb{R}$ we have
$\|\theta_{i}X_{i}\|_{\eta_{3}-0.5\iota}\leq
K_{1}|\theta_{i}|\sigma_{X,\eta_{3}-0.5\iota}/d_{i}$. So,

$\displaystyle\|\theta^{\top}X\|_{\eta_{3}-0.5\iota}\leq
K_{1}\sigma_{X,\eta_{3}-0.5\iota}\sum_{i=1}^{d}\frac{|\theta_{i}|}{d_{i}}\leq\frac{K_{1}\sigma_{X,\eta_{3}-0.5\iota}\sum_{i=1}^{d}\frac{|\theta_{i}|}{d_{i}}}{\sigma_{0}\sqrt{\sum_{i=1}^{d}\frac{\theta_{i}^{2}}{d_{i}^{2}}}}\|\theta^{\top}X\|_{2}$
(26) $\displaystyle\leq$
$\displaystyle\frac{K_{1}\sigma_{X,\eta_{3}-0.5\iota}\sqrt{d}}{\sigma_{0}}\|\theta^{\top}X\|_{2}.$
(27)

Then from Lemma 4.1 of [Men15] we have that the condition (b) of Assumption
2.1 is true here.

  * •

Since $\upsilon_{i}$ and $X_{i}$ are independent, and
$\mathbb{E}\left[\upsilon_{i}\right]=0$, we have
$\mathbb{E}\left[\upsilon_{i}t^{\top}X_{i}\right]=0$. Let
$\eta_{2}=\min(\eta_{3},\eta_{4})$. Then using Markov’s inequality, for any
$t\in{\cal H}_{R}$ and $\forall i$, we have,

$\displaystyle\mathbb{P}\left(\left\lvert\upsilon_{i}t^{\top}X_{i}-\mathbb{E}\left[\upsilon_{i}t^{\top}X_{i}\right]\right\rvert\geq\tau\right)\leq\frac{\|\upsilon_{i}\|_{\eta_{2}}^{\eta_{2}}\left(\sum_{j=1}^{d}\|t_{j}X_{i,j}\|_{\eta_{2}}\right)^{\eta_{2}}}{\tau^{\eta_{2}}}\leq\frac{\left(R\sigma_{\upsilon}\sigma_{X,\eta_{2}}d_{H}\right)^{\eta_{2}}}{\tau^{\eta_{2}}},$

where $d_{H}=\sum_{i=1}^{d}d_{j}^{-1}$, and for all $i,j$,
$\|\upsilon_{i}\|_{\eta_{2}}=\sigma_{\upsilon}$, and
$\|X_{i,j}\|_{\eta_{2}}=\sigma_{X,\eta_{2}}/d_{j}$. This implies that
condition (c)-(ii) of Assumption 2.1 is true in this setting.

######  Proposition 4.2.

Consider the learning problem described in Section 4.2. Then with probability
at least (14), we have,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{1}{4}\left(1-\frac{1}{\eta_{2}}\right)+\iota},\frac{C_{9}R}{\tau
Q_{{\cal
H}_{R}}(2\tau)^{3/2}}d^{1/(\eta_{2}-0.5\iota)+\iota/8}N^{-1/2+\iota}\right\\}.$
(28)

The proof of Proposition 4.2 could be found in the Appendix D.2.

######  Remark 4.

Note that the heaviness of the tail dominates the exponential $\beta$-mixing
rate $\eta_{1}$ in determining the rates of convergence. Observe that as
$\eta_{2}\to\infty$ all the moments exist, and $N^{-(1-1/\eta_{2})/4+\iota}\to
N^{-1/4+\iota}$. This rate is the same as the one that we obtain under
condition (c)-(i), although with weaker polynomial probability. Furthermore,
the dimension dependency is polynomial here. On a related note, [ZZ18]
analyzes $\ell_{1}$-regression with a truncated loss in the
$\operatorname*{\texttt{iid}}$ setting with the assumption $\eta_{2}>2$ and
gets $\sqrt{d/N}$ rate with exponential probability. We point out that in the
$\operatorname*{\texttt{iid}}$ setting Medians-of-mean method achieves the
optimal rate with exponential probability under the stronger assumption that
$\log d$ moments exist [LM19].

###  4.3 Example 3: $\beta$-mixing sub-Gaussian data and Pareto noise with
Huber Loss

In this example, we consider Huber loss which satisfies Assumption 3.2:

$\displaystyle\ell_{T_{h}}(t)=\begin{cases}t^{2}/2&\text{if}\left\lvert
t\right\rvert\leq T_{h}\\\ T_{h}\left\lvert t\right\rvert-
T_{h}^{2}/2&\text{if}\left\lvert t\right\rvert\geq T_{h}\,.\end{cases}$

We now formally establish the benefits of using Huber loss when the noise
$\xi$ has a polynomial tail but $(f-f^{*})(X)$ has a sub-Weibull tail. Let
$\\{\delta_{i}\\}_{i\in\mathbb{Z^{+}}}$ be an $\operatorname*{\texttt{iid}}$
sequence of $d$-dimensional standard Gaussian random vectors $\delta_{i}\sim
N(0,I_{d})$. To compare the performance of ERM under Huber loss to that of
squared loss, for simplicity, we allow $X$ to be Gaussian; but a similar
result will hold for sub-Weibull $\delta_{i}$. Assume that the input vectors
are generated according to (19) where $A$ is a $d\times d$ matrix with
spectral radius less than $1$. For simplicity, let $A=\sigma_{0}^{2}I_{d}$
where $\sigma_{0}^{2}<1$. [WZLL20] showed that this time series is stable,
strict sense stationary, with $X_{i}\sim N(0,1/(1-\sigma_{0}^{4})I_{d})$. Let
$\\{Y_{i}\\}_{i\in\mathbb{Z^{+}}}$, be the response sequence given by
$Y_{i}={\theta^{*}}^{\top}X_{i}+\xi_{i}$, where $\theta^{*}\in B_{1}^{d}(R)$,
$\ell_{1}$-norm ball in $\mathbb{R}^{d}$. Let $\\{\xi_{i}\\}_{i=1}^{n}$ be
independent of $X_{i}$ for all $i$, and be an $\operatorname*{\texttt{iid}}$
sequence of $0$ mean random variables with heavy tails such that for all
$t>0$, $\mathbb{P}\left(|\xi_{i}|\geq t\right)\leq 1/(1+t^{\eta_{4}})$,
$\eta_{4}>2+2\iota$ and $\textsc{var}(\xi)\leq\sigma_{\xi}$. Set
$T_{h}=3\sigma_{\xi}$. We verify the required assumptions for this example in
the following section.

####  4.3.1 Verification of Assumptions for Example 4.3

Condition (a) of Assumption 2.1 and condition (b) of Assumption 2.2 are true
here by the same argument as in Example 4.1. This also implies that Assumption
3.1 is true in this case for $p=8$. Since we consider Huber loss, a lipschitz
continuous loss, we have $l^{\prime}(\xi)\leq\min(|\xi/2|,T_{h})$. Set
$T_{h}=c_{11}(\kappa_{0}+1/\sqrt{\epsilon})(\sigma_{\xi}+2R)$. As an immediate
consequence of [VGNA20, Proposition 2.3], we have that condition (c)-(i) in
Assumption 2.2 is valid here with $\eta_{2}=2$. Note that if a sequence is
exponentially $\beta$-mixing, i.e., satisfies condition (a) of Assumption 2.1
with coefficient $\eta_{1}>0$, then the same condition is true for all
$\eta<\eta_{1}$. So choosing $\eta_{1}^{\prime}<\eta_{2}/(\eta_{2}-1)$ we get
Condition (d) of Assumption 2.1 is true.

######  Proposition 4.3.

Consider the learning problem described in Section 4.3. Then, for some
constant $c_{12}>0$, with probability at least

$\displaystyle
1-c_{9}\epsilon^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{10}\epsilon^{1+\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}}-\widetilde{C}_{2}N{\rm
exp}\left(-(N^{2\iota}\tau_{0})^{\eta}/M_{1}\right),$

we have

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{1}{2}+\iota},c_{12}R\sqrt{\log(ed/N)}N^{-\frac{1}{2}}\right\\}.$

The proof of Proposition 4.3 could be found in the Appendix E.

######  Remark 5.

In this setting, using squared loss would mean that condition (c)-(ii) of
Assumption 2.1 is true. So, by part 2 of Theorem 3.1, the obtained rate would
be of order $N^{-1/8}$ with polynomial probability given by (14), which is
significantly worse than that of Proposition 4.3 with Huber loss.

##  5 Proof Sketch of Theorem 3.1 and 3.2

Recall the decomposition (1). The first and the last terms in the RHS of (1)
are handled respectively by condition (b) and (c) of Assumption 2.1. The basic
idea is to show that if for some $f\in{\cal F}$, $\|f-f^{*}\|_{L_{2}}$ is
large, then with high probability
$T_{1}:=N^{-1}\sum_{i=1}^{N}(f-f^{*})^{2}(X_{i})\geq\underline{B}$ (Lemma B.1)
and $T_{2}:=2N^{-1}\sum_{i=1}^{N}\xi_{i}(f-f^{*})(X_{i})\geq\bar{B}$ (see
(68)) where $\underline{B}+\bar{B}>0$. But since $\hat{f}$ minimizes
$P_{N}L_{f}$ and $f^{*}\in{\cal F}$, $P_{N}L_{f}\leq 0$. So with high
probability $\|\hat{f}-f^{*}\|_{L_{2}}$ is small. In contrast to [Men15], we
face two major challenges: 1- For the lower bound on $T_{1}$, the
symmetrization argument used in the $\operatorname*{\texttt{iid}}$ case (e.g.
[Men15, Men18]) is not applicable under our dependency structure. 2- For the
term $T_{2}$, [Men15, Men18] use the complexity measure
$\alpha_{N}^{*}(\gamma,\delta)$ (see (108)) in the
$\operatorname*{\texttt{iid}}$ case to control the noise-input interactions,
which is not possible to do in our setting; our analysis to control $T_{2}$ is
different, through which we can show how different tail conditions on the data
and noise affect the high-probability statements on the learning rate. The
proof of Theorem 3.2 for the locally strongly-convex loss functions, follows a
similar strategy. However, the technical details become more involved.

##  6 Conclusion

In this work, we analyzed the performance of empirical risk minimization with
squared error and convex loss functions, when the DGP is both dependent
(specifically, exponentially $\beta$-mixing) and heavy-tailed. We derived
explicit rates using a combination of small-ball method and concentration
inequalities. We demonstrated the applicability of our results on a high-
dimensional linear regression problem, and showed that our assumptions are
easily verified for a certain classes of sub-Weibull and Pareto DGP. Our
results clearly show the benefits of using Huber loss over the squared error
loss for ERM with heavy-tailed data in our setting. For future work, we plan
to study median-of-means based techniques and examine establishing similar
rates of convergence for dependent heavy-tailed data.

## References

  * [Ace02] Carlo Acerbi, _Spectral measures of risk: A coherent representation of subjective risk aversion_ , Journal of Banking & Finance 26 (2002), no. 7, 1505–1518.
  * [ALW13] Pierre Alquier, Xiaoyin Li, and Olivier Wintenberger, _Prediction of time series by statistical learning: General losses and fast rates_ , Dependence Modeling 1 (2013), no. 2013, 65–93.
  * [AV90] David Aldous and Umesh Vazirani, _A Markovian extension of Valiant’s learning model_ , Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, IEEE, 1990, pp. 392–396.
  * [AW12] Pierre Alquier and Olivier Wintenberger, _Model selection for weakly dependent time series forecasting_ , Bernoulli 18 (2012), no. 3, 883–913.
  * [BBM05] Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson, _Local Rademacher complexities_ , The Annals of Statistics 33 (2005), no. 4, 1497–1537.
  * [BF89] Graciela Boente and Ricardo Fraiman, _Robust nonparametric regression estimation for dependent observations_ , The Annals of Statistics (1989), 1242–1256.
  * [BL97] Rakesh D Barve and Philip M Long, _On the complexity of learning from drifting distributions_ , Information and Computation 138 (1997), no. 2, 170–193.
  * [BM21] Daniel Bartl and Shahar Mendelson, _On Monte-Carlo methods in convex stochastic optimization_ , arXiv preprint arXiv:2101.07794 (2021).
  * [BMdlP20] Milad Bakhshizadeh, Arian Maleki, and Victor H de la Pena, _Sharp concentration results for heavy-tailed distributions_ , arXiv preprint arXiv:2003.13819 (2020).
  * [BR97] Patrizia Berti and Pietro Rigo, _A Glivenko-Cantelli theorem for exchangeable random variables_ , Statistics & probability letters 32 (1997), no. 4, 385–391.
  * [Bra05] Richard C Bradley, _Basic properties of strong mixing conditions. a survey and some open questions_ , arXiv preprint math/0511078 (2005).
  * [CG14] Kacper Chwialkowski and Arthur Gretton, _A kernel independence test for random processes_ , International Conference on Machine Learning, PMLR, 2014, pp. 1422–1430.
  * [Che07] Christophe Chesneau, _A tail bound for sums of independent random variables: application to the symmetric pareto distribution_.
  * [DDDJ19] Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Siddhartha Jayanti, _Learning from weakly dependent data under Dobrushin’s condition_ , Conference on Learning Theory, PMLR, 2019, pp. 914–928.
  * [DKBR07] Murat Dundar, Balaji Krishnapuram, Jinbo Bi, and R Bharat Rao, _Learning classifiers when the training data is not IID._ , IJCAI, vol. 2007, 2007, pp. 756–61.
  * [DP04] Jérôme Dedecker and Clémentine Prieur, _Coupling for $\tau$-dependent sequences and applications_, Journal of Theoretical Probability 17 (2004), no. 4, 861–885.
  * [DT20] A Philip Dawid and Ambuj Tewari, _On learnability under general stochastic processes_ , arXiv preprint arXiv:2005.07605 (2020).
  * [FS12] Amir-massoud Farahmand and Csaba Szepesvári, _Regularized least-squares regression: Learning from a $\beta$-mixing sequence_, Journal of Statistical Planning and Inference 142 (2012), no. 2, 493–505.
  * [Gam03] David Gamarnik, _Extension of the PAC framework to finite and countable markov chains_ , IEEE Transactions on Information Theory 49 (2003), no. 1, 338–345.
  * [GM20] Peter D Grünwald and Nishant A Mehta, _Fast rates for general unbounded loss functions: From ERM to Generalized Bayes._ , Journal of Machine Learning Research 21 (2020), no. 56, 1–80.
  * [Han21] Steve Hanneke, _Learning whenever learning is possible: Universal learning under general stochastic processes_ , Journal of Machine Learning Research (to appear) (2021).
  * [HH21] Matthew J Holland and El Mehdi Haress, _Spectral risk-based learning using unbounded losses_ , arXiv preprint arXiv:2105.04816 (2021).
  * [HS14] Hanyuan Hang and Ingo Steinwart, _Fast learning from $\alpha$-mixing observations_, Journal of Multivariate Analysis 127 (2014), 184–199.
  * [Hub92] Peter J Huber, _Robust estimation of a location parameter_ , Breakthroughs in statistics, Springer, 1992, pp. 492–518.
  * [HW19] Qiyang Han and Jon A Wellner, _Convergence rates of least squares regression estimators with heavy-tailed errors_ , Annals of Statistics 47 (2019), no. 4, 2286–2319.
  * [Irl97] A Irle, _On consistency in nonparametric estimation under mixing conditions_ , Journal of multivariate analysis 60 (1997), no. 1, 123–147.
  * [JM01] Jiancheng Jiang and YP Mack, _Robust local polynomial regression for dependent data_ , Statistica Sinica (2001), 705–722.
  * [KDD+21] Vardis Kandiros, Yuval Dagan, Nishanth Dikkala, Surbhi Goel, and Constantinos Daskalakis, _Statistical estimation from dependent data_ , International Conference on Machine Learning, PMLR, 2021, pp. 5269–5278.
  * [KM17] Vitaly Kuznetsov and Mehryar Mohri, _Generalization bounds for non-stationary mixing processes_ , Machine Learning 106 (2017), no. 1, 93–117.
  * [Kol06] Vladimir Koltchinskii, _Local Rademacher complexities and oracle inequalities in risk minimization_ , Annals of Statistics 34 (2006), no. 6, 2593–2656.
  * [Kol11] , _Oracle inequalities in empirical risk minimization and sparse recovery problems_ , vol. 2033, Springer Science & Business Media, 2011.
  * [LL20] Guillaume Lecué and Matthieu Lerasle, _Robust machine learning by median-of-means: theory and practice_ , Annals of Statistics 48 (2020), no. 2, 906–931.
  * [LM18] Guillaume Lecué and Shahar Mendelson, _Regularization and the small-ball method I: Sparse recovery_ , The Annals of Statistics 46 (2018), no. 2, 611–641.
  * [LM19] Gábor Lugosi and Shahar Mendelson, _Regularization, sparse recovery, and median-of-means tournaments_ , Bernoulli 25 (2019), no. 3, 2075–2106.
  * [Loh17] Po-Ling Loh, _Statistical consistency and asymptotic normality for high-dimensional robust $m$-estimators_, The Annals of Statistics 45 (2017), no. 2, 866–896.
  * [LRS15] Tengyuan Liang, Alexander Rakhlin, and Karthik Sridharan, _Learning with square loss: Localization through offset Rademacher complexity_ , Conference on Learning Theory, PMLR, 2015, pp. 1260–1285.
  * [LT13] Michel Ledoux and Michel Talagrand, _Probability in banach spaces: isoperimetry and processes_ , Springer Science & Business Media, 2013.
  * [Mei00] Ron Meir, _Nonparametric time series prediction through adaptive model selection_ , Machine learning 39 (2000), no. 1, 5–34.
  * [Men15] Shahar Mendelson, _Learning without concentration_ , Journal of the ACM (JACM) 62 (2015), no. 3, 1–25.
  * [Men17a] , _Local vs. global parameters: Breaking the Gaussian complexity barrier_ , Annals of statistics 45 (2017), no. 5, 1835–1862.
  * [Men17b] , _On multiplier processes under weak moment assumptions_ , Geometric aspects of functional analysis, Springer, 2017, pp. 301–318.
  * [Men18] , _Learning without concentration for general loss functions_ , Probability Theory and Related Fields 171 (2018), no. 1, 459–502.
  * [MGW20] Zakaria Mhammedi, Benjamin Guedj, and Robert C Williamson, _Pac-bayesian bound for the conditional value at risk_ , arXiv preprint arXiv:2006.14763 (2020).
  * [MM19] Stanislav Minsker and Timothée Mathieu, _Excess risk bounds in robust empirical risk minimization_ , arXiv preprint arXiv:1910.07485 (2019).
  * [Mok88] Abdelkader Mokkadem, _Mixing properties of arma processes_ , Stochastic processes and their applications 29 (1988), no. 2, 309–315.
  * [MPR11] Florence Merlevède, Magda Peligrad, and Emmanuel Rio, _A Bernstein type inequality and moderate deviations for weakly dependent sequences_ , Probability Theory and Related Fields 151 (2011), no. 3-4, 435–474.
  * [MR08] Mehryar Mohri and Afshin Rostamizadeh, _Rademacher complexity bounds for Non-IID processes_ , Proceedings of the 21st International Conference on Neural Information Processing Systems, 2008, pp. 1097–1104.
  * [MS11] Daniel J McDonald and Cosma Rohilla Shalizi, _Rademacher complexity of stationary sequences_ , arXiv preprint arXiv:1106.0730 (2011).
  * [MZ20] Shahar Mendelson and Nikita Zhivotovskiy, _Robust covariance estimation under $l_{4}$-$l_{2}$ norm equivalence_, Annals of Statistics 48 (2020), no. 3, 1648–1664.
  * [Nob99] Andrew B Nobel, _Limits to classification and regression estimation from ergodic processes_ , The Annals of Statistics 27 (1999), no. 1, 262–273.
  * [Pes10] Vladimir Pestov, _Predictive PAC learnability: A paradigm for learning from exchangeable input data_ , 2010 IEEE International Conference on Granular Computing, IEEE, 2010, pp. 387–391.
  * [Pil91] RN Pillai, _Semi-pareto processes_ , Journal of applied probability (1991), 461–465.
  * [Ris08] Miroslav M Ristić, _A generalized semi-pareto minification process_ , Statistical Papers 49 (2008), no. 2, 343–351.
  * [RS06] Andrzej Ruszczyński and Alexander Shapiro, _Optimization of convex risk functions_ , Mathematics of operations research 31 (2006), no. 3, 433–452.
  * [RS14] Alexander Rakhlin and Karthik Sridharan, _Online non-parametric regression_ , Conference on Learning Theory, PMLR, 2014, pp. 1232–1264.
  * [RSS10] Liva Ralaivola, Marie Szafranski, and Guillaume Stempfel, _Chromatic PAC-Bayes bounds for non-IID data: Applications to ranking and stationary $\beta$-mixing processes_, The Journal of Machine Learning Research 11 (2010), 1927–1956.
  * [RST15] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari, _Sequential complexities and uniform martingale laws of large numbers_ , Probability Theory and Related Fields 161 (2015), no. 1-2, 111–153.
  * [RU02] R Tyrrell Rockafellar and Stanislav Uryasev, _Conditional value-at-risk for general loss distributions_ , Journal of banking & finance 26 (2002), no. 7, 1443–1471.
  * [SHS09] Ingo Steinwart, Don Hush, and Clint Scovel, _Learning from dependent observations_ , Journal of Multivariate Analysis 100 (2009), no. 1, 175–194.
  * [SY20] Tasuku Soma and Yuichi Yoshida, _Statistical learning with conditional value at risk_ , arXiv preprint arXiv:2002.05826 (2020).
  * [VC71] Vladimir Vapnik and Aleksei Chervonenkis, _On uniform convergence of the frequencies of events to their probabilities_ , Teoriya Veroyatnostei i ee Primeneniya 16 (1971), no. 2, 264–279.
  * [vdG00] Sara van de Geer, _Empirical processes in m-estimation_ , vol. 6, Cambridge university press, 2000.
  * [VDVW96] Aad W Van Der Vaart and Jon A Wellner, _Weak convergence_ , Weak convergence and empirical processes, Springer, 1996, pp. 16–28.
  * [VGNA20] Mariia Vladimirova, Stéphane Girard, Hien Nguyen, and Julyan Arbel, _Sub-Weibull distributions: Generalizing sub-Gaussian and sub-Exponential properties to heavier tailed distributions_ , Stat 9 (2020), no. 1, e318.
  * [Vid13] Mathukumalli Vidyasagar, _Learning and generalisation: With applications to neural networks_ , Springer Science & Business Media, 2013.
  * [VK06] Mathukumalli Vidyasagar and Rajeeva L Karandikar, _A learning theory approach to system identification and stochastic adaptive control_ , Probabilistic and randomized methods for design under uncertainty, Springer, 2006, pp. 265–302.
  * [WLT20] Kam Chung Wong, Zifan Li, and Ambuj Tewari, _Lasso guarantees for $\beta$-mixing heavy-tailed time series_, Annals of Statistics 48 (2020), no. 2, 1124–1142.
  * [WZLL20] Di Wang, Yao Zheng, Heng Lian, and Guodong Li, _High-dimensional vector autoregressive time series modeling via tensor decomposition_ , 2020.
  * [Yu94] Bin Yu, _Rates of convergence for empirical processes of stationary mixing sequences_ , The Annals of Probability (1994), 94–116.
  * [ZCY12] Yongquan Zhang, Feilong Cao, and Canwei Yan, _Learning rates of least-square regularized regression with strongly mixing observation_ , International Journal of Machine Learning and Cybernetics 3 (2012), no. 4, 277–283.
  * [ZZ18] Lijun Zhang and Zhi-Hua Zhou, _$\ell_{1}$ -regression with heavy-tailed distributions_, Proceedings of the 32nd International Conference on Neural Information Processing Systems, 2018, pp. 1084–1094.

##  Appendix A Proof of Lemma 2.2

######  Lemma A.1 (Concentration for heavy-tailed $\beta$-mixing sum, Lemma
2.2).

Let $\\{W_{j}\\}_{j\geq 1}$ be a sequence of zero-mean real valued random
variables satisfying conditions (a) and (c)-(ii) of Assumption 2.1, for some
$\eta_{2}>2$. Then for any positive integer $N$, $0\leq d_{1}\leq 1$, and
$d_{2}\geq 0$, and for any $t>1$, we have,

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i=1}^{j}W_{i}\right\rvert\geq t\right)\leq$
$\displaystyle\frac{2^{\eta_{2}+3}}{(d_{2}\log
t)^{\frac{1-\eta_{2}}{\eta_{1}}}}\frac{N}{t^{(1+d_{1}(\eta_{2}-1))}}+8\frac{N}{t^{(1+c^{\prime}d_{2})}}+2e^{-\frac{t^{2-2d_{1}}(d_{2}\log
t)^{1/\eta_{1}}}{9N}},$

where $c^{\prime}>0$ is a constant.

Proof. [Proof of Lemma 2.2] Let $W_{i,M}$ denote the truncated random variable
$W_{i}$ such that $W_{i,M}=\max(\min(W_{i},M),-M)$. Then define
$\Sigma_{N}:=\sum_{i=1}^{N}W_{i}$. Consider the partition of the samples into
blocks of length $A$, $I_{i}=\\{1+(i-1)A,\cdots,iA\\}$ for
$i=1,2,\cdots,2\mu_{1}$ where $\mu_{1}=\left[N/(2A)\right]$. Also let
$I_{2\mu_{1}+1}=\\{2\mu_{1}A+1,\cdots,N\\}$. Define for a finite set $I$ of
positive integers, define $\Sigma_{N,M}(I)=\sum_{i\in I}W_{i,M}$. Then we can
write, for $j\leq N$

$\displaystyle\Sigma_{j}=$ $\displaystyle\sum_{i=1}^{j}W_{i}$ (29)
$\displaystyle=$
$\displaystyle\sum_{i=1}^{j}(W_{i}-W_{i,M})+\sum_{i=1}^{j}W_{i,M}$ (30)
$\displaystyle=$
$\displaystyle\sum_{i=1}^{j}(W_{i}-W_{i,M})+\sum_{i\leq[j/A]}\Sigma_{N,M}(I_{2i})+\sum_{i\leq[j/A]}\Sigma_{N,M}(I_{2i-1})+\sum_{i=A[j/A]+1}^{j}W_{i,M}.$
(31)

Then we have,

$\displaystyle\left\lvert\Sigma_{j}\right\rvert$
$\displaystyle\leq\sum_{i=1}^{j}\left\lvert
W_{i}-W_{i,M}\right\rvert+\left\lvert\sum_{i\leq[j/A]}\Sigma_{N,M}(I_{2i})\right\rvert+\left\lvert\sum_{i\leq[j/A]}\Sigma_{N,M}(I_{2i-1})\right\rvert+2AM$
(32) $\displaystyle\sup_{j\leq N}\left\lvert\Sigma_{j}\right\rvert$
$\displaystyle\leq\sum_{i=1}^{N}\left\lvert
W_{i}-W_{i,M}\right\rvert+\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma_{N,M}(I_{2i})\right\rvert+\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma_{N,M}(I_{2i-1})\right\rvert+2AM.$ (33)

Now we will establish concentration for each of the terms in the above
expression. Using Markov’s inequality,

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{N}\left\lvert
W_{i}-W_{i,M}\right\rvert\geq t\right)$
$\displaystyle\leq\frac{1}{t}\sum_{i=1}^{N}\mathbb{E}\left[\left\lvert
W_{i}-W_{i,M}\right\rvert\right]\leq\frac{2}{t}\sum_{i=1}^{N}\int_{M}^{\infty}\mathbb{P}(\left\lvert
W_{i}\right\rvert\geq x)dx$
$\displaystyle\leq\frac{2N}{t}\int_{M}^{\infty}x^{-\eta_{2}}dx=\frac{2N}{t(\eta_{2}-1)}M^{1-\eta_{2}}.$
(34)

Using Lemma 5 of [DP04], we get independent random variables
$\\{\Sigma^{*}_{N,M}(I_{2i})\\}_{1\leq i\leq\mu_{1}}$, where
$\Sigma^{*}_{N,M}(I_{2i})$ has the same distribution as
$\Sigma_{N,M}(I_{2i})$, such that,

$\displaystyle\mathbb{E}\left[\left\lvert\Sigma_{N,M}(I_{2i})-\Sigma^{*}_{N,M}(I_{2i})\right\rvert\right]\leq
A\tau(A).$ (35)

Then, using Markov’s inequality we have,

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma_{N,M}(I_{2i})\right\rvert\geq t\right)$
$\displaystyle\leq$ $\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}(\Sigma_{N,M}(I_{2i})-\Sigma^{*}_{N,M}(I_{2i}))\right\rvert+\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\geq
t\right)$ $\displaystyle\leq$ $\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}(\Sigma_{N,M}(I_{2i})-\Sigma^{*}_{N,M}(I_{2i}))\right\rvert\geq\frac{t}{2}\right)+\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\geq\frac{t}{2}\right)$
$\displaystyle\leq$ $\displaystyle\frac{2\mathbb{E}\left[\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}(\Sigma_{N,M}(I_{2i})-\Sigma^{*}_{N,M}(I_{2i}))\right\rvert\right]}{t}+\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\geq\frac{t}{2}\right)$
$\displaystyle\leq$ $\displaystyle\frac{2\mathbb{E}\left[\sup_{j\leq
N}\sum_{i\leq\mu_{1}}\left\lvert\Sigma_{N,M}(I_{2i})-\Sigma^{*}_{N,M}(I_{2i})\right\rvert\right]}{t}+\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\geq\frac{t}{2}\right)$
$\displaystyle\leq$
$\displaystyle\frac{2A\mu_{1}\tau(A)}{t}+\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\geq\frac{t}{2}\right).$

The same results holds for
$\\{\Sigma^{*}_{N,M}(I_{2i-1})\\}_{i=1,2,\cdots,k}$. So for any $t\geq 2AM$,
we have,

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\Sigma_{j}\right\rvert\geq 6t\right)\leq$
$\displaystyle\frac{2N}{t(\eta_{2}-1)}M^{1-\eta_{2}}+\frac{4A\mu_{1}\tau(A)}{t}+\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\geq
t\right)$ $\displaystyle~{}~{}+\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i-1})\right\rvert\geq
t\right).$ (36)

Now, for $\lambda>0$

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\geq
t\right)$ $\displaystyle\leq e^{-\lambda t}\mathbb{E}\left[{\rm
exp}\left(\lambda\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\right)\right]$
$\displaystyle\leq e^{-\lambda t}\mathbb{E}\left[{\rm
exp}\left(\lambda\sum_{i\leq\mu_{1}}\left\lvert\Sigma^{*}_{N,M}(I_{2i})\right\rvert\right)\right]$
$\displaystyle\leq e^{-\lambda t}\Pi_{i=1}^{\mu_{1}}\mathbb{E}\left[{\rm
exp}\left(\lambda\left\lvert\Sigma_{N,M}(I_{2i})\right\rvert\right)\right].$

We have $\left\lvert\Sigma_{N,M}(I_{2i})\right\rvert\leq AM$. So
$\left\lvert\Sigma_{N,M}(I_{2i})\right\rvert$ is a sub-gaussian random
variable and consequently,

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\geq
t\right)\leq e^{-\lambda t}e^{\frac{\lambda^{2}\mu_{1}A^{2}M^{2}}{2}}.$

Optimizing over $\lambda>0$ we have,

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i})\right\rvert\geq
t\right)\leq e^{-\frac{t^{2}}{2\mu_{1}A^{2}M^{2}}}.$ (37)

Similarly, we also obtain

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\sum_{i\leq[j/A]}\Sigma^{*}_{N,M}(I_{2i-1})\right\rvert\geq
t\right)\leq e^{-\frac{t^{2}}{2\mu_{1}A^{2}M^{2}}}.$ (38)

From (36), (37), and (38) we have,

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\Sigma_{j}\right\rvert\geq 6t\right)\leq$
$\displaystyle\frac{2N}{t(\eta_{2}-1)}M^{1-\eta_{2}}+\frac{4A\mu_{1}\tau(A)}{t}+2e^{-\frac{t^{2}}{2\mu_{1}A^{2}M^{2}}}.$

Condition (a) in Assumption 2.1 implies that the process
$\\{Z_{i}\\}_{i=-\infty}^{\infty}$ is exponentially $\tau$-mixing [CG14],
i.e., for a constant $c^{\prime}>0$, $\tau(k)\leq
e^{-c^{\prime}k^{\eta_{1}}}$. Then we have

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\Sigma_{j}\right\rvert\geq t\right)\leq$
$\displaystyle\frac{12N}{t(\eta_{2}-1)}M^{1-\eta_{2}}+\frac{24A\mu_{1}{\rm
exp}(-c^{\prime}A^{\eta_{1}})}{t}+2e^{-\frac{t^{2}}{72\mu_{1}A^{2}M^{2}}}.$

As $2A\mu_{1}\leq N\leq 3A\mu_{1}$ and $\eta_{2}>2$,

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\Sigma_{j}\right\rvert\geq t\right)\leq$
$\displaystyle\frac{12NM^{1-\eta_{2}}}{t}+\frac{8N{\rm
exp}(-c^{\prime}A^{\eta_{1}})}{t}+2e^{-\frac{t^{2}}{36NAM^{2}}}.$

Now choosing

$\displaystyle M=\frac{t^{d_{1}}}{2(d_{2}\log t)^{\frac{1}{\eta_{1}}}},\quad
A=\left(d_{2}\log t\right)^{\frac{1}{\eta_{1}}},\qquad 0\leq d_{1}\leq 1,\quad
d_{2}\geq 0,$ (39)

we have, $2AM\leq t$, and

$\displaystyle\mathbb{P}\left(\sup_{j\leq
N}\left\lvert\Sigma_{j}\right\rvert\geq t\right)\leq$
$\displaystyle\frac{2^{\eta_{2}+3}}{(d_{2}\log
t)^{\frac{1-\eta_{2}}{\eta_{1}}}}Nt^{-(1+d_{1}(\eta_{2}-1))}+8Nt^{-(1+d_{2}c^{\prime})}+2e^{-\frac{t^{2-2d_{1}}(d_{2}\log
t)^{1/\eta_{1}}}{9N}}.$

##  Appendix B Proofs of Section 3

###  B.1 Proofs for squared error loss

Similar to the decomposition (1), for squared loss we have

$\displaystyle
P_{N}L_{f}=\frac{1}{N}\sum_{i=1}^{N}(f-f^{*})^{2}(X_{i})+\frac{2}{N}\sum_{i=1}^{N}\xi_{i}(f-f^{*})(X_{i}),\vspace{-.05in}$

Since ${\cal F}$ is convex, we also have

$\displaystyle\mathbb{E}\left[\xi(f-f^{*})(X)\right]\geq 0.$

Then,

$\displaystyle
P_{N}L_{f}\geq\frac{1}{N}\sum_{i=1}^{N}(f-f^{*})^{2}(X_{i})+\frac{2}{N}\sum_{i=1}^{N}(\xi_{i}(f-f^{*})(X_{i})-\mathbb{E}\left[\xi_{i}(f-f^{*})(X_{i})\right]).\vspace{-.05in}$
(40)

Now our goal is to establish a lower bound (Lemma B.1) on the first term of
the RHS of (40), and a two-sided bound ((68) and (70)) on the second term when
$\|f-f^{*}\|_{L_{2}}$ is large. Combining these bounds we will show that if
$\|f-f^{*}\|_{L_{2}}$ is large then $P_{N}L_{f}>0$ which implies $f$ cannot be
a minimizer of empirical risk because for the minimizer $\hat{f}$ we have
$P_{N}L_{\hat{f}}\leq 0$.

######  Lemma B.1.

Let Condition (a) and (b) of Assumption 2.1 be true. Given $f^{*}\in{\cal F}$,
set ${\cal H}={\cal F}-f^{*}$. Then, for every $\rho>\omega_{\mu}({\cal
H},\tau Q_{\cal H}(2\tau)/16)$, with probability at least $\mathscr{P}_{1}$,
if $\|f-f^{*}\|_{L_{2}}\geq\rho$, we have,

$\displaystyle\left\lvert\\{i:\left\lvert(f-f^{*})(X_{i})\right\rvert\geq\tau\|f-f^{*}\|_{L_{2}}\\}\right\rvert\geq\frac{NQ_{\cal
H}(2\tau)}{4}.$ (41)

The proof of Lemma B.1 follows easily by combining the results of Lemma B.2,
and Corollary B.1 which we state next.

######  Lemma B.2.

Let $S(L_{2})$ be the $L_{2}(\pi)$ unit sphere and let ${\cal H}\subset
S(L_{2})$. Consider the partition in (6). Under conditions (a) and (b) of
Assumption 2.1, by setting $\mu=\frac{NQ_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4\mathscr{G}(N)^{\frac{1}{\eta_{1}}}}$ for
some $\mathscr{G}(N)\leq\frac{cQ_{\cal
H}(2\tau)^{\eta_{1}}N^{\eta_{1}}}{4^{\eta_{1}}}$, if,

$\displaystyle\mathfrak{R}_{\mu}({\cal H})\leq\frac{\tau Q_{\cal
H}(2\tau)N}{16\mu},$ (42)

then with probability at least $1-2{\rm exp}\left(-\frac{NQ_{\cal
H}(2\tau)^{3}}{2(4-Q_{\cal
H}(2\tau))^{2}}\left(\frac{c}{\mathscr{G}(N)}\right)^{\frac{1}{\eta_{1}}}\right)-\frac{NQ_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4\mathscr{G}(N)^{\frac{1}{\eta_{1}}}}{\rm
exp}(-\mathscr{G}(N))$, we have

$\displaystyle\inf_{h\in{\cal H}}\left\lvert\\{i:\left\lvert
h(X_{i})\right\rvert\geq\tau\\}\right\rvert\geq$ $\displaystyle\frac{NQ_{\cal
H}(2\tau)}{4}.$ (43)

######  Remark 6.

We have the following illustrative instantiations of Lemma B.2:

  1. 1.

If one sets $\mathscr{G}(N)=k\log N\leq\frac{cQ_{\cal
H}(2\tau)^{\eta_{1}}N^{\eta_{1}}}{4^{\eta_{1}}}$, then the statement of Lemma
B.2 holds as long as,

$\displaystyle\mathfrak{R}_{\mu}({\cal H})\leq\frac{\tau(k\log
N)^{\frac{1}{\eta_{1}}}}{4c^{\frac{1}{\eta_{1}}}},$ (44)

with probability at least

$1-2{\rm exp}\left(-\frac{NQ_{\cal H}(2\tau)^{3}}{2(4-Q_{\cal
H}(2\tau))^{2}}\left(\frac{c}{k\log
N}\right)^{\frac{1}{\eta_{1}}}\right)-\frac{N^{1-k}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4(k\log N)^{\frac{1}{\eta_{1}}}}.$

  2. 2.

If one sets $\mathscr{G}(N)=N^{r}\leq\frac{cQ_{\cal
H}(2\tau)^{\eta_{1}}N^{\eta_{1}}}{4^{\eta_{1}}}$, for some $0<r<\eta_{1}$,
then the statement of Lemma B.2 holds as long as,

$\displaystyle\mathfrak{R}_{\mu}({\cal
H})\leq\frac{\tau(N)^{\frac{r}{\eta_{1}}}}{4c^{\frac{1}{\eta_{1}}}},$ (45)

with probability at least

$1-2{\rm exp}\left(-\frac{NQ_{\cal H}(2\tau)^{3}}{2(4-Q_{\cal
H}(2\tau))^{2}}\left(\frac{c}{N^{r}}\right)^{\frac{1}{\eta_{1}}}\right)-\frac{NQ_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4(N)^{\frac{r}{\eta_{1}}}}{\rm exp}(-N^{r}).$

Proof. [Proof of Lemma B.2] Let $\psi_{u}:\mathbb{R}_{+}\rightarrow[0,1]$ be
the function

$\displaystyle\psi_{u}(t)=\begin{cases}1&\quad t\geq 2u,\\\
\frac{t}{u}-1&\quad u\leq t\leq 2u\\\ 0&\quad t<u\end{cases}$

Similar to (6), let us define sequences of i.i.d blocks
$\\{\tilde{Z}_{i}^{(a)}\\}_{i=1}^{\mu}$, and
$\\{\tilde{Z}_{i}^{(b)}\\}_{i=1}^{\mu}$ where the samples within each block
are assumed to be drawn from the same $\beta$-mixing distribution of
$\\{{Z}_{i}^{(a)}\\}_{i=1}^{\mu}$, and $\\{{Z}_{i}^{(b)}\\}_{i=1}^{\mu}$. Let
$\tilde{S}_{a}=\left(\tilde{Z}_{1}^{(a)},\cdots,\tilde{Z}_{\mu}^{(a)}\right)$,
and
$\tilde{S}_{b}=\left(\tilde{Z}_{1}^{(b)},\cdots,\tilde{Z}_{\mu}^{(b)}\right)$.
Now let us concentrate on the term $\left\lvert
P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert$.

$\displaystyle\left\lvert P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert$
$\displaystyle\leq$
$\displaystyle\left\lvert\frac{1}{N}\sum_{i=1}^{N}\psi_{u}(h(|X_{i}|))-P\psi_{u}(|h|)\right\rvert$
$\displaystyle\leq$
$\displaystyle\left\lvert\frac{1}{N}\sum_{i=1}^{\mu}\sum_{j=1}^{a}\psi_{u}(|h(X_{(i-1)(a+b)+j})|)+\frac{1}{N}\sum_{i=1}^{\mu}\sum_{j=1}^{b}\psi_{u}(h(|X_{(i-1)(a+b)+a+j}|))-P\psi_{u}(|h|)\right\rvert$
$\displaystyle\leq$
$\displaystyle\left\lvert\frac{1}{N}\sum_{i=1}^{\mu}\sum_{j=1}^{a}\left(\psi_{u}(h(|X_{(i-1)(a+b)+j}|))-P\psi_{u}(|h|)\right)\right\rvert+\frac{b\mu}{N}.$
(46)

Using (46) and Corollary 2.7 of [Yu94], for some $a,b,\mu$ to be chosen later
such that $(a+b)\mu=N$ we have,

$\displaystyle{\mathbb{P}}\left(\left\lvert
P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert\geq t+\frac{b\mu}{N}\right)$
(47) $\displaystyle\leq$
$\displaystyle{\mathbb{P}}\left(\left\lvert\frac{1}{N}\sum_{i=1}^{\mu}\sum_{j=1}^{a}\left(\psi_{u}(h(|X_{(i-1)(a+b)+j}|))-P\psi_{u}(|h|)\right)\right\rvert+\frac{b\mu}{N}\geq
t+\frac{b\mu}{N}\right)$ (48) $\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbbm{1}\left(\left\lvert\frac{1}{N}\sum_{i=1}^{\mu}\sum_{j=1}^{a}\left(\psi_{u}(h(|X_{(i-1)(a+b)+j}|))-P\psi_{u}(|h|)\right)\right\rvert\geq
t\right)\right]$ (49) $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\mathbbm{1}\left(\left\lvert\frac{1}{N}\sum_{i=1}^{\mu}\sum_{j=1}^{a}\left(\psi_{u}(h(|\tilde{X}_{(i-1)(a+b)+j}|))-P\psi_{u}(|h|)\right)\right\rvert\geq
t\right)\right]+(\mu-1)\beta(b)$ (50) $\displaystyle=$
$\displaystyle{\mathbb{P}}\left(\left\lvert\frac{1}{N}\sum_{i=1}^{\mu}\sum_{j=1}^{a}\left(\psi_{u}(h(|\tilde{X}_{(i-1)(a+b)+j}|))-P\psi_{u}(|h|)\right)\right\rvert\geq
t\right)+(\mu-1)\beta(b)$ (51) $\displaystyle=$
$\displaystyle{\mathbb{P}}\left(\left\lvert\frac{1}{\mu}\sum_{i=1}^{\mu}\tilde{\psi}(\tilde{Z}_{i}^{(a)})\right\rvert\geq\frac{Nt}{\mu}\right)+(\mu-1)\beta(b),$
(52)

where

$\tilde{\psi}(\tilde{Z}_{i}^{(a)})=\sum_{j=1}^{a}\left(\psi_{u}(h(|\tilde{X}_{(i-1)(a+b)+j}|))-P\psi_{u}(|h|)\right),$

and $\mathbbm{1}(\cdot)$ is the indicator function. Observe that the function

$W(\tilde{Z}_{1}^{(a)},\tilde{Z}_{2}^{(a)},\cdots,\tilde{Z}_{\mu}^{(a)})=\mu^{-1}\sum_{i=1}^{\mu}\tilde{\psi}(\tilde{Z}_{i}^{(a)})$

has bounded difference with coefficient $2a/\mu$. Then using Mcdiarmid’s
bounded-difference inequality on
$W(\tilde{Z}_{1}^{(a)},\tilde{Z}_{2}^{(a)},\cdots,\tilde{Z}_{\mu}^{(a)})$ we
get,

$\displaystyle{\mathbb{P}}\left(\left\lvert\frac{1}{\mu}\sum_{i=1}^{\mu}\tilde{\psi}(\tilde{Z}_{i}^{(a)})\right\rvert\geq\frac{Nt}{\mu}\right)\leq
2{\rm exp}\left(-\frac{N^{2}t^{2}}{2a^{2}\mu}\right).$ (53)

Combining (52), and (53), we get

$\displaystyle{\mathbb{P}}\left(\left\lvert
P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert\geq t+\frac{b\mu}{N}\right)\leq
2{\rm exp}\left(-\frac{N^{2}t^{2}}{2a^{2}\mu}\right)+(\mu-1)\beta(b),$

which implies

$\displaystyle{\mathbb{P}}\left(\left\lvert
P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert\geq\frac{4\mu}{Nu}\mathbb{R}_{\mu}({\cal
H})+\frac{b\mu}{N}+\frac{t}{\sqrt{N}}\right)$ $\displaystyle\leq$
$\displaystyle 2{\rm
exp}\left(-\frac{N^{2}\left(\frac{4\mu}{Nu}\mathbb{R}_{\mu}({\cal
H})+\frac{t}{\sqrt{N}}\right)^{2}}{2a^{2}\mu}\right)+(\mu-1)\beta(b).$

Also note that, for any $t$, we have $\left\lvert
P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert\geq t$ which implies that we
also have $\sup_{h\in{\cal H}}\left\lvert
P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert\geq t$. Hence,

$\displaystyle{\mathbb{P}}\left(\sup_{h\in{\cal H}}\left\lvert
P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert\geq\frac{4\mu}{Nu}\mathbb{R}_{\mu}({\cal
H})+\frac{b\mu}{N}+\frac{t}{\sqrt{N}}\right)$ $\displaystyle\leq$
$\displaystyle 2{\rm
exp}\left(-\frac{N^{2}\left(\frac{4\mu}{Nu}\mathbb{R}_{\mu}({\cal
H})+\frac{t}{\sqrt{N}}\right)^{2}}{2a^{2}\mu}\right)+(\mu-1)\beta(b).$ (54)

In other words, with probability at least $1-2{\rm
exp}\left(-\frac{N^{2}\left(\frac{4\mu}{Nu}\mathbb{R}_{\mu}({\cal
H})+\frac{t}{\sqrt{N}}\right)^{2}}{2a^{2}\mu}\right)-(\mu-1)\beta(b)$, we have

$\displaystyle\sup_{h\in{\cal H}}\left\lvert
P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert\leq\frac{4\mu}{Nu}\mathbb{R}_{\mu}({\cal
H})+\frac{b\mu}{N}+\frac{t}{\sqrt{N}}.$ (55)

Hence, we have

$\displaystyle P_{N}\mathbf{1}_{\\{|h|\geq u\\}}\geq\inf_{h\in{\cal
H}}{\mathbb{P}}(|h|\geq 2u)-\sup_{h\in{\cal H}}\left\lvert
P_{N}\psi_{u}(|h|)-P\psi_{u}(|h|)\right\rvert.$ (56)

So, combining (54), and (56), with probability at least $1-2{\rm
exp}\left(-\frac{N^{2}\left(\frac{4\mu}{Nu}\mathbb{R}_{\mu}({\cal
H})+\frac{t}{\sqrt{N}}\right)^{2}}{2a^{2}\mu}\right)-(\mu-1)\beta(b)$ we have

$\displaystyle P_{N}\mathbf{1}_{\\{|h|\geq u\\}}\geq$
$\displaystyle\inf_{h\in{\cal H}}{\mathbb{P}}(|h|\geq
2u)-\frac{4\mu}{Nu}\mathbb{R}_{\mu}({\cal
H})-\frac{b\mu}{N}-\frac{t}{\sqrt{N}}.$

Now, setting

$\displaystyle u=\tau\quad t=\frac{\sqrt{N}Q_{\cal H}}{4}\quad
a=\frac{(4-Q_{\cal H}(2\tau))(\mathscr{G}(N))^{\frac{1}{\eta_{1}}}}{Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}\quad
b=\left(\frac{\mathscr{G}(N)}{c}\right)^{\frac{1}{\eta_{1}}}\quad\mu=\frac{NQ_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4\mathscr{G}(N)^{\frac{1}{\eta_{1}}}},$ (57)

and using the condition $\mathscr{G}(N)>c$, we get, with probability at least

$1-2{\rm exp}\left(-\frac{NQ_{\cal H}(2\tau)^{3}}{2(4-Q_{\cal
H}(2\tau))^{2}}\left(\frac{c}{\mathscr{G}(N)}\right)^{\frac{1}{\eta_{1}}}\right)-\frac{NQ_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4\mathscr{G}(N)^{\frac{1}{\eta_{1}}}}{\rm
exp}(-\mathscr{G}(N)),$

we have

$\displaystyle P_{N}\mathbf{1}_{\\{|h|\geq u\\}}\geq\frac{Q_{\cal
H}(2\tau)}{4}.$

######  Corollary B.1.

Let Condition (a) and (b) of Assumption 2.1 be true. Let ${\cal H}$ be star-
shaped around $0$ and assume that there is some $\tau>0$ for which $Q_{\cal
H}(2\tau)>0$. Then for every $\rho>\omega_{\mu}({\cal H},\tau Q_{\cal
H}(2\tau)/16)$, with probability at least

$\mathscr{P}_{1}\coloneqq 1-2{\rm exp}\left(-\frac{NQ_{\cal
H}(2\tau)^{3}}{2(4-Q_{\cal
H}(2\tau))^{2}}\left(\frac{c}{\mathscr{G}(N)}\right)^{\frac{1}{\eta_{1}}}\right)-\frac{NQ_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4\mathscr{G}(N)^{\frac{1}{\eta_{1}}}}{\rm
exp}(-\mathscr{G}(N)),$

for every $h\in{\cal H}$ that satisfies $\|h\|_{L_{2}}\geq\rho$,

$\displaystyle\left\lvert\\{i:\left\lvert
h(X_{i})\right\rvert\geq\tau\|h\|_{L_{2}}\\}\right\rvert\geq N\frac{Q_{\cal
H}(2\tau)}{4}.$ (58)

Proof. [Proof of Corollary B.1] Let $\rho>\omega_{\mu}({\cal H},\tau Q_{\cal
H}(2\tau)/16)$ and as ${\cal H}$ is star-shaped around $0$,

$\displaystyle\mathfrak{R}_{\mu}({\cal H}\cap\rho\mathcal{D})\leq\frac{\tau
Q_{\cal H}(2\tau)}{16}\rho.$ (59)

Consider the set,

$\displaystyle V=\\{h/\rho:h\in{\cal H}\cap\rho S(L_{2})\\}\subset S(L_{2}).$
(60)

Clearly, $Q_{V}(2\tau)\geq Q_{\cal H}(2\tau)$ and

$\displaystyle\mathfrak{R}_{\mu}(V)=\mathbb{E}\left[\sup_{h\in{\cal H}\cap\rho
S(L_{2})}\left\lvert\frac{1}{\mu}\sum_{i=1}^{\mu}\epsilon_{i}\frac{h(\tilde{X}_{i})}{\rho}\right\rvert\right]\leq\frac{\tau
Q_{\cal H}(2\tau)}{16}\leq\frac{\tau Q_{V}(2\tau)}{16}.$ (61)

Using Lemma B.2 on the set $V$, we get with probability at least
$\mathscr{P}_{1}$, for every $v\in V$

$\displaystyle\inf_{h\in{\cal
H}}\left\lvert\\{i:|v(X_{i})\geq\tau|\\}\right\rvert\geq\frac{NQ_{V}(2\tau)}{4}\geq\frac{NQ_{\cal
H}(2\tau)}{4}.$

Now for any $h$ with $\|h\|_{L_{2}}\geq\rho$, since ${\cal H}$ is star-shaped
around $0$, we have $(\rho/\|h\|_{L_{2}})h\in{\cal H}\cap\rho S(L_{2})$ which
implies, $h/\|h\|_{L_{2}}\in V$. So we have (58).

######  Theorem B.1 (Restatement of Theorem 3.1).

Consider the LS-ERM procedure. For $\tau_{0}<\tau^{2}Q_{\cal H}(2\tau)/8$,
setting $\mu=\frac{N^{r}Q_{\cal H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4}$, for some
constants $c,c^{\prime}>0$, and $0<r<1$, we have, for any $N\geq 4$,

  1. 1.

under condition (a), (b), (c)-(i), and (d) of Assumption 2.1, for $\
0<\iota<\frac{1}{4}$,

$\displaystyle\left(\int(\hat{f}-f^{*})^{2}d\pi\right)^{\frac{1}{2}}=\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{1}{4}+\iota},\omega_{\mu}({\cal
F}-{\cal F},\tau Q_{{\cal F}-{\cal F}}(2\tau)/16)\right\\}$ (62)

with probability at least

$\displaystyle 1-$ $\displaystyle 2{\rm exp}\left(-\frac{N^{r}Q_{\cal
H}(2\tau)^{3}c^{\frac{1}{\eta_{1}}}}{2(4-Q_{\cal
H}(2\tau))^{2}}\right)-\frac{N^{r}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4}{\rm exp}(-N^{(1-r)\eta_{1}})-N{\rm
exp}\left(-\frac{(N^{\frac{1}{2}+2\iota}\tau_{0})^{\eta}}{C_{1}}\right)$
$\displaystyle-$ $\displaystyle{\rm
exp}\left(-\frac{N^{1+4\iota}\tau_{0}^{2}}{C_{2}(1+NV)}\right)-{\rm
exp}\left(-\frac{N^{4\iota}\tau_{0}^{2}}{C_{3}}{\rm
exp}\left((1-\eta)^{\eta}\frac{(N^{\frac{1}{2}+2\iota}\tau_{0})^{\frac{\eta(1-\eta)}{2}}}{C_{4}2^{\eta}}\right)\right),$
(63)

where $V$ is defined in (8) and $C_{1},C_{2},C_{3}$ are some positive
constants.

  2. 2.

under condition (a), (b), and (c)-(ii) of Assumption 2.1, for $\
0<\iota<(1-1/\eta_{2})/4$,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{1}{4}\left(1-\frac{1}{\eta_{2}}\right)+\iota},\omega_{\mu}({\cal
F}-{\cal F},\tau Q_{{\cal F}-{\cal F}}(2\tau)/16)\right\\}$ (64)

with probability at least

$\displaystyle 1-2{\rm exp}\left(-\frac{N^{r}Q_{\cal
H}(2\tau)^{3}c^{\frac{1}{\eta_{1}}}}{2(4-Q_{\cal
H}(2\tau))^{2}}\right)-\frac{N^{r}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4}{\rm
exp}(-N^{(1-r)\eta_{1}})-8\tau_{0}^{-\frac{2\eta_{2}}{1+\eta_{2}}}N^{-\frac{4\iota\eta_{2}}{1+\eta_{2}}}$
$\displaystyle-\frac{2^{\eta_{2}+3}{c^{\prime}}^{\frac{1-\eta_{2}}{\eta_{1}}}\tau_{0}^{-\frac{2\eta_{2}}{1+\eta_{2}}}}{\left(\log\left(\tau_{0}N^{\frac{1}{2}+\frac{1}{2\eta_{2}}+2\iota}\right)/2\right)^{\frac{1-\eta_{2}}{\eta_{1}}}}N^{-\frac{4\iota\eta_{2}}{1+\eta_{2}}}-2e^{-\frac{\tau_{0}^{\frac{2\eta_{2}}{1+\eta_{2}}}\left(\log\left(\tau_{0}N^{\frac{1}{2}+\frac{1}{2\eta_{2}}+2\iota}\right)/2\right)^{1/\eta_{1}}}{9{c^{\prime}}^{1/\eta_{1}}}N^{\frac{4\iota\eta_{2}}{1+\eta_{2}}}}$
(65)

Proof. [Proof of Theorem B.1] We first prove Part 1. We will denote the class
${\cal F}-f^{*}$ by ${\cal H}$. From Lemma B.2 it follows that if
$\rho>\omega_{\mu}({\cal H},\tau Q_{{\cal F}-{\cal F}}(2\tau)/16)$, then with
probability at least

$\mathscr{P}_{1}=1-2{\rm exp}\left(-\frac{NQ_{\cal H}(2\tau)^{3}}{2(4-Q_{\cal
H}(2\tau))^{2}}\left(\frac{c}{\mathscr{G}(N)}\right)^{\frac{1}{\eta_{1}}}\right)-\frac{NQ_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4\mathscr{G}(N)^{\frac{1}{\eta_{1}}}}{\rm
exp}(-\mathscr{G}(N)),$

for every $f\in{\cal F}$ that satisfies $\|f-f^{*}\|_{L_{2}}\geq\rho$,

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}(f-f^{*})^{2}(X_{i})\geq\frac{\tau^{2}\|f-f^{*}\|^{2}_{L_{2}}Q_{\cal
H}(2\tau)}{4}.$ (66)

So, with probability at least $\mathscr{P}_{1}$, for every $f\in{\cal F}$ that
satisfies $\|f-f^{*}\|_{L_{2}}\geq\rho$,

$\displaystyle P_{N}\mathcal{L}_{f}\geq
2\left(\frac{1}{N}\sum_{i=1}^{N}\xi_{i}(f-f^{*})(X_{i})-\mathbb{E}\left[\xi(f-f^{*})\right]\right)+\frac{\tau^{2}\|f-f^{*}\|^{2}_{L_{2}}Q_{\cal
H}(2\tau)}{4}.$ (67)

When $\|f-f^{*}\|_{L_{2}}\geq\mathscr{A}(N)>2(N\tau_{0})^{-1/2}$, we have
$\log(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})\leq
2(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{(1-\eta)/2}/(1-\eta)$. Under Conditions
(a), (c)-(i), and (d) of Assumption 2.1, using Lemma 2.1, we get

$\displaystyle{\mathbb{P}}\left(\left\lvert\frac{1}{N}\sum_{i=1}^{N}\xi_{i}(f-f^{*})(X_{i})-\mathbb{E}\left[\xi(f-f^{*})\right]\right\rvert\geq\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}\right)$
$\displaystyle\leq$ $\displaystyle N{\rm
exp}\left(-\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta}}{C_{1}}\right)+{\rm
exp}\left(-\frac{N^{2}\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{2}(1+NV)}\right)$
$\displaystyle~{}+{\rm
exp}\left(-\frac{N\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{3}}{\rm
exp}\left(\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta(1-\eta)}}{C_{4}(\log(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}))^{\eta}}\right)\right)$
$\displaystyle\leq$ $\displaystyle N{\rm
exp}\left(-\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta}}{C_{1}}\right)+{\rm
exp}\left(-\frac{N^{2}\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{2}(1+NV)}\right)$
$\displaystyle~{}+{\rm
exp}\left(-\frac{N\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{3}}{\rm
exp}\left(\frac{(1-\eta)^{\eta}(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\frac{{\eta(1-\eta)}}{2}}}{C_{4}2^{\eta}}\right)\right)$
$\displaystyle\leq$ $\displaystyle N{\rm
exp}\left(-\frac{(N\tau_{0}\mathscr{A}(N)^{2})^{\eta}}{C_{1}}\right)+{\rm
exp}\left(-\frac{N^{2}\tau_{0}^{2}\mathscr{A}(N)^{4}}{C_{2}(1+NV)}\right)$
$\displaystyle~{}+{\rm
exp}\left(-\frac{N\tau_{0}^{2}\mathscr{A}(N)^{4}}{C_{3}}{\rm
exp}\left(\frac{(1-\eta)^{\eta}(N\tau_{0}\mathscr{A}(N)^{2})^{\frac{{\eta(1-\eta)}}{2}}}{C_{4}2^{\eta}}\right)\right)\equiv\mathscr{P}_{2},$
(68)

where

$V\leq\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{2}\right]+4\sum_{i\geq
0}\mathbb{E}\left[B_{i}\left(\xi_{1}(f-f^{*})(X_{1})\right)^{2}\right],$

$\\{B_{i}\\}$ is some sequence such that $B_{i}\in[0,1]$,
$\mathbb{E}\left[B_{i}\right]\leq\beta(i)$ and $C_{1},C_{2},C_{3}$ are
constants which depend on $c,\eta,\eta_{1},\eta_{2}$. Observe that,

$\displaystyle V\leq$
$\displaystyle\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{2}\right]+4\sum_{i\geq
0}\mathbb{E}\left[B_{i}\left(\xi_{1}(f-f^{*})(X_{1})\right)^{2}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{2}\right]+4\sum_{i\geq
0}\sqrt{\mathbb{E}\left[B_{i}^{2}\right]\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{4}\right]}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{2}\right]+4\sqrt{\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{4}\right]}\sum_{i\geq
0}\sqrt{\mathbb{E}\left[B_{i}\right]}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{2}\right]+4\sqrt{\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{4}\right]}\sum_{i\geq
0}\sqrt{\beta(i)}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{2}\right]+4\sqrt{\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{4}\right]}\sum_{i\geq
0}{\rm exp}(-ci^{\eta_{1}}/2)$ $\displaystyle\leq$ $\displaystyle
2^{\frac{2}{\eta_{2}}}+C4^{1+\frac{2}{\eta_{2}}}.$

Combining (67), and (68), with probability at least
$\mathscr{P}_{1}-\mathscr{P}_{2}$, for every $f\in{\cal F}$ that satisfies
$\|f-f^{*}\|_{L_{2}}\geq\max(\rho,\mathscr{A}(N))$, we get

$\displaystyle
P_{N}L_{f}\geq-2\tau_{0}\|f-f^{*}\|^{2}_{L_{2}}+\frac{\tau^{2}\|f-f^{*}\|^{2}_{L_{2}}Q_{\cal
H}(2\tau)}{4}.$

Choosing $\tau_{0}<\tau^{2}Q_{\cal H}(2\tau)/8$, we have,

$P_{N}L_{f}>0.$

But the empirical minimizer $\hat{f}$ satisfies $P_{N}L_{\hat{f}}\leq 0$. This
implies, together with choosing $\mathscr{A}(N)=N^{-1/4+\iota}$, that with
probability at least $\mathscr{P}=\mathscr{P}_{1}-\mathscr{P}_{2}$,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max(\omega_{\mu}({\cal F}-{\cal
F},\tau Q_{{\cal F}-{\cal F}}(2\tau)/16),\mathscr{A}(N)),$

where

$\displaystyle\mathscr{P}=1-2{\rm exp}\left(-\frac{NQ_{\cal
H}(2\tau)^{3}}{2(4-Q_{\cal
H}(2\tau))^{2}}\left(\frac{c}{\mathscr{G}(N)}\right)^{\frac{1}{\eta_{1}}}\right)-\frac{NQ_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4\mathscr{G}(N)^{\frac{1}{\eta_{1}}}}{\rm
exp}(-\mathscr{G}(N))$ $\displaystyle-$ $\displaystyle N{\rm
exp}\left(-\frac{(N^{\frac{1}{2}+2\iota}\tau_{0})^{\eta}}{C_{1}}\right)-{\rm
exp}\left(-\frac{N^{1+4\iota}\tau_{0}^{2}}{C_{2}(1+NV)}\right)-{\rm
exp}\left(-\frac{N^{4\iota}\tau_{0}^{2}}{C_{3}}{\rm
exp}\left((1-\eta)^{\eta}\frac{(N^{\frac{1}{2}+2\iota}\tau_{0})^{\frac{\eta(1-\eta)}{2}}}{C_{4}2^{\eta}}\right)\right).$

Choosing $\mathscr{G}(N)=N^{(1-r)\eta_{1}}$ for some $0<r<1$, we get,

$\displaystyle\mathscr{P}=$ $\displaystyle 1-2{\rm
exp}\left(-\frac{N^{r}Q_{\cal H}(2\tau)^{3}c^{\frac{1}{\eta_{1}}}}{2(4-Q_{\cal
H}(2\tau))^{2}}\right)-\frac{N^{r}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4}{\rm exp}(-N^{(1-r)\eta_{1}})$
$\displaystyle~{}-N{\rm
exp}\left(-\frac{(N^{\frac{1}{2}+2\iota}\tau_{0})^{\eta}}{C_{1}}\right)-{\rm
exp}\left(-\frac{N^{1+4\iota}\tau_{0}^{2}}{C_{2}(1+NV)}\right)$
$\displaystyle~{}-{\rm exp}\left(-\frac{N^{4\iota}\tau_{0}^{2}}{C_{3}}{\rm
exp}\left((1-\eta)^{\eta}\frac{(N^{\frac{1}{2}+2\iota}\tau_{0})^{\frac{\eta(1-\eta)}{2}}}{C_{4}2^{\eta}}\right)\right),$

and

$\displaystyle\mu=\frac{N^{r}Q_{\cal H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4}.$
(69)

We now prove part 2. Since Lemma B.1 only depends on Condition (a) and (b) of
Assumption 2.1, Lemma B.1 remains unchanged in this case. To deal with the
multiplier process we need a concentration result similar to Lemma 2.1. So we
use the concentration inequality we proved in Lemma 2.2. When
$\|f-f^{*}\|_{L_{2}}\geq\mathscr{A}(N)$, using Lemma 2.2 we have

$\displaystyle{\mathbb{P}}\left(\left\lvert\frac{1}{N}\sum_{i=1}^{N}\xi_{i}(f-f^{*})(X_{i})-\mathbb{E}\left[\xi(f-f^{*})\right]\right\rvert\geq\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}\right)$
$\displaystyle\leq$ $\displaystyle\frac{2^{\eta_{2}+3}}{(d_{2}\log
N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\frac{1-\eta_{2}}{\eta_{1}}}}N(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{-(1+d_{1}(\eta_{2}-1))}+8N(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{-(1+d_{2}c^{\prime})}$
$\displaystyle+2e^{-\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{2-2d_{1}}(d_{2}\log(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}))^{1/\eta_{1}}}{9N}}$
$\displaystyle\leq$
$\displaystyle\frac{2^{\eta_{2}+3}}{(d_{2}\log(N\tau_{0}\mathscr{A}(N)^{2}))^{\frac{1-\eta_{2}}{\eta_{1}}}}N(N\tau_{0}\mathscr{A}(N)^{2})^{-(1+d_{1}(\eta_{2}-1))}+8N(N\tau_{0}\mathscr{A}(N)^{2})^{-(1+d_{2}c^{\prime})}$
$\displaystyle+2e^{-\frac{(N\tau_{0}\mathscr{A}(N)^{2})^{2-2d_{1}}(d_{2}\log(N\tau_{0}\mathscr{A}(N)^{2}))^{1/\eta_{1}}}{9N}}\equiv\mathscr{P}_{2}.$
(70)

We will choose $d_{1}$ suitably to allow $\mathscr{A}(N)$ to decrease with $N$
as fast as possible while ensuring $\lim_{N\to\infty}\mathscr{P}_{2}\to 0$.
Combining (67), and (70), with probability at least
$\mathscr{P}_{1}-\mathscr{P}_{2}$, for every $f\in{\cal F}$ that satisfies
$\|f-f^{*}\|_{L_{2}}\geq\max(\rho,\mathscr{A}(N))$, we get

$\displaystyle
P_{N}L_{f}\geq-2\tau_{0}\|f-f^{*}\|^{2}_{L_{2}}+\frac{\tau^{2}\|f-f^{*}\|^{2}_{L_{2}}Q_{\cal
H}(2\tau)}{4}.$

Choosing $\tau_{0}<\tau^{2}Q_{\cal H}(2\tau)/8$, we have,

$P_{N}L_{f}>0.$

But the empirical minimizer $\hat{f}$ satisfies $P_{N}L_{\hat{f}}\leq 0$. This
implies, together with choosing $\mathscr{A}(N)=N^{-(1-1/\eta_{2})/4+\iota}$,
$d_{1}=1/(1+\eta_{2})$, $d_{2}=(\eta_{2}-1)/(\eta_{2}+1)$, and
$\iota<(1-1/\eta_{2})/4$, that with probability at least
$\mathscr{P}=\mathscr{P}_{1}-\mathscr{P}_{2}$,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max(\omega_{\mu}({\cal F}-{\cal
F},\tau Q_{{\cal F}-{\cal F}}(2\tau)/16),\mathscr{A}(N)),$

where

$\displaystyle\mathscr{P}$ $\displaystyle=1-2{\rm exp}\left(-\frac{NQ_{\cal
H}(2\tau)^{3}}{2(4-Q_{\cal
H}(2\tau))^{2}}\left(\frac{c}{\mathscr{G}(N)}\right)^{\frac{1}{\eta_{1}}}\right)-\frac{NQ_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4\mathscr{G}(N)^{\frac{1}{\eta_{1}}}}{\rm
exp}(-\mathscr{G}(N))$
$\displaystyle-\frac{2^{\eta_{2}+3}\tau_{0}^{-\frac{2\eta_{2}}{1+\eta_{2}}}}{\left(\log\left(\tau_{0}N^{\frac{1}{2}+\frac{1}{2\eta_{2}}+2\iota}\right)/2\right)^{\frac{1-\eta_{2}}{\eta_{1}}}}N^{-\frac{4\iota\eta_{2}}{1+\eta_{2}}}-8\tau_{0}^{-\frac{2\eta_{2}}{1+\eta_{2}}}N^{-\frac{4\iota\eta_{2}}{1+\eta_{2}}}-2e^{-\frac{\tau_{0}^{\frac{2\eta_{2}}{1+\eta_{2}}}\left(\log\left(\tau_{0}N^{\frac{1}{2}+\frac{1}{2\eta_{2}}+2\iota}\right)/2\right)^{1/\eta_{1}}}{9}N^{\frac{4\iota\eta_{2}}{1+\eta_{2}}}}.$

Choosing $\mathscr{G}(N)=N^{(1-r)\eta_{1}}$ for some $0<r<1$, we get,

$\displaystyle\mathscr{P}=$ $\displaystyle 1-2{\rm
exp}\left(-\frac{N^{r}Q_{\cal H}(2\tau)^{3}c^{\frac{1}{\eta_{1}}}}{2(4-Q_{\cal
H}(2\tau))^{2}}\right)-\frac{N^{r}Q_{\cal
H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4}{\rm exp}(-N^{(1-r)\eta_{1}})$
$\displaystyle-$
$\displaystyle\frac{2^{\eta_{2}+3}\tau_{0}^{-\frac{2\eta_{2}}{1+\eta_{2}}}}{\left(\log\left(\tau_{0}N^{\frac{1}{2}+\frac{1}{2\eta_{2}}+2\iota}\right)/2\right)^{\frac{1-\eta_{2}}{\eta_{1}}}}N^{-\frac{4\iota\eta_{2}}{1+\eta_{2}}}-8\tau_{0}^{-\frac{2\eta_{2}}{1+\eta_{2}}}N^{-\frac{4\iota\eta_{2}}{1+\eta_{2}}}-2e^{-\frac{\tau_{0}^{\frac{2\eta_{2}}{1+\eta_{2}}}\left(\log\left(\tau_{0}N^{\frac{1}{2}+\frac{1}{2\eta_{2}}+2\iota}\right)/2\right)^{1/\eta_{1}}}{9}N^{\frac{4\iota\eta_{2}}{1+\eta_{2}}}},$

and

$\displaystyle\mu=\frac{N^{r}Q_{\cal H}(2\tau)c^{\frac{1}{\eta_{1}}}}{4}.$
(71)

Proof. [Proof of Corollary 3.1] Note that Assumption 3.1 implies Condition (b)
of Assumption 2.1 as shown in Lemma 4.1 in [Men15]. Under Assumption 3.1 with
$p=8$, using Cauchy-Schwarz inequality we have,

$\displaystyle V\leq$
$\displaystyle\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{2}\right]+4\sqrt{\mathbb{E}\left[\left(\xi_{1}(f-f^{*})(X_{1})\right)^{4}\right]}\sum_{i\geq
0}{\rm exp}(-ci^{\eta_{1}}/2)$ $\displaystyle\leq$
$\displaystyle\sqrt{\mathbb{E}\left[\xi_{1}^{4}\right]}\sqrt{\mathbb{E}\left[\left((f-f^{*})(X_{1})\right)^{4}\right]}+4C\sqrt{\sqrt{\mathbb{E}\left[\xi_{1}^{8}\right]}\sqrt{\mathbb{E}\left[\left((f-f^{*})(X_{1})\right)^{8}\right]}}$
$\displaystyle\leq$ $\displaystyle
M_{1}^{2}\|f-f^{*}\|_{L_{2}}^{2}\left(\sqrt{\mathbb{E}\left[\xi_{1}^{4}\right]}+4C\left(\mathbb{E}\left[\xi_{1}^{8}\right]\right)^{\frac{1}{4}}\right)$
$\displaystyle\leq$ $\displaystyle M_{2}^{2}\|f-f^{*}\|_{L_{2}}^{2},$

for some constant $M_{2}$. Then, from (68) we have,

$\displaystyle{\mathbb{P}}\left(\left\lvert\frac{1}{N}\sum_{i=1}^{N}\xi_{i}(f-f^{*})(X_{i})-\mathbb{E}\left[\xi(f-f^{*})\right]\right\rvert\geq\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}\right)$
$\displaystyle\leq$ $\displaystyle N{\rm
exp}\left(-\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta}}{C_{1}}\right)+{\rm
exp}\left(-\frac{N^{2}\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{2}(1+NV)}\right)$
$\displaystyle~{}+{\rm
exp}\left(-\frac{N\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{3}}{\rm
exp}\left(\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta(1-\eta)}}{C_{4}(\log(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}))^{\eta}}\right)\right)$
$\displaystyle\leq$ $\displaystyle N{\rm
exp}\left(-\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta}}{C_{1}}\right)+{\rm
exp}\left(-\frac{N^{2}\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{2}(1+NM_{2}^{2}\|f-f^{*}\|_{L_{2}}^{2})}\right)$
$\displaystyle~{}+{\rm
exp}\left(-\frac{N\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{3}}{\rm
exp}\left(\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta(1-\eta)}}{C_{4}(\log(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}))^{\eta}}\right)\right).$

If $N\|f-f^{*}\|_{L_{2}}^{2}\geq
N\mathscr{A}(N)^{2}\geq\max(1/M_{2}^{2},1/\tau_{0})$, then

$\displaystyle{\mathbb{P}}\left(\left\lvert\frac{1}{N}\sum_{i=1}^{N}\xi_{i}(f-f^{*})(X_{i})-\mathbb{E}\left[\xi(f-f^{*})\right]\right\rvert\geq\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}\right)$
$\displaystyle\leq$ $\displaystyle N{\rm
exp}\left(-\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta}}{C_{1}}\right)+{\rm
exp}\left(-\frac{N\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{2}}{2C_{2}M_{2}^{2}}\right)$
$\displaystyle+{\rm
exp}\left(-\frac{N\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{3}}{\rm
exp}\left(\frac{(1-\eta)^{\eta}(N\tau_{0}\mathscr{A}(N)^{2})^{\frac{{\eta(1-\eta)}}{2}}}{C_{4}2^{\eta}}\right)\right),$

and the second term dominates the third term in the above expression. Now if
choose $\mathscr{A}(N)=N^{-1/2+\iota}$, then with probability at least

$\displaystyle\mathscr{P}=1-{\rm
exp}\left(-\frac{N^{2\iota}\tau_{0}^{2}}{2C_{2}M_{2}^{2}}\right)-{\rm
exp}\left(-\frac{N^{4\iota-1}\tau_{0}^{2}}{C_{3}}{\rm
exp}\left(\frac{(1-\eta)^{\eta}(N^{2\iota}\tau_{0})^{\frac{{\eta(1-\eta)}}{2}}}{C_{4}2^{\eta}}\right)\right),$

we get

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left(N^{-1/2+\iota},\omega_{\mu}({\cal
F}-{\cal F},\tau Q_{{\cal F}-{\cal F}}(2\tau)/16)\right).$

###  B.2 Proofs for convex loss

Recall the decomposition (1)

$\displaystyle
P_{N}L_{f}\geq\frac{1}{16N}\sum_{i=1}^{N}\ell^{\prime\prime}(\widetilde{\xi}_{i})(f-f^{*})^{2}(X_{i})+\frac{1}{N}\sum_{i=1}^{N}\ell^{\prime}(\xi_{i})(f-f^{*})(X_{i}).\vspace{-.05in}$

Since ${\cal F}$ is convex, we also have

$\displaystyle\mathbb{E}\left[\ell^{\prime}(\xi)(f-f^{*})(X)\right]\geq 0.$

Then,

$\displaystyle
P_{N}L_{f}\geq\frac{1}{16N}\sum_{i=1}^{N}\ell^{\prime\prime}(\widetilde{\xi}_{i})(f-f^{*})^{2}(X_{i})+\frac{1}{N}\sum_{i=1}^{N}(\ell^{\prime}(\xi_{i})(f-f^{*})(X_{i})-\mathbb{E}\left[\ell^{\prime}(\xi_{i})(f-f^{*})(X_{i})\right]).\vspace{-.05in}$
(72)

Now our goal is to establish a lower bound (Proposition B.1) on the first term
of the RHS of (72), and a two-sided bound ((94) and (95)) on the second term
when $\|f-f^{*}\|_{L_{2}}$ is large. Combining these bounds we will show that
if $\|f-f^{*}\|_{L_{2}}$ is large then $P_{N}L_{f}>0$ which implies $f$ cannot
be a minimizer of empirical risk because for the minimizer $\hat{f}$ we have
$P_{N}L_{\hat{f}}\leq 0$. Let
$\rho(t_{1},t_{2})\coloneqq\inf\\{l^{\prime\prime}(x):x\in[t_{1},t_{2}],0\leq
t_{1}<t_{2}\\}$. First we prove the following extension of bounded difference
inequality to the $\beta$-mixing sequence which we will use frequently in our
proofs.

######  Lemma B.3 (Bounded difference inequality for strictly stationary
$\beta$-mixing sequence).

Let $\\{U_{i}\\}_{i=1}^{N}$ be a sample from a strictly stationary
$\beta$-mixing sequence, $|U_{i}|\leq M$, and
$\mathbb{E}\left[U_{i}\right]=U^{*}$. Let $N>a,b,\mu>0$ be such that
$(a+b)\mu=N$. Then with probability at least $1-{\rm
exp}\left(-\frac{(t-2b\mu)^{2}}{2\mu a^{2}M^{2}}\right)-2M(\mu-1)\beta(b)$, we
have $\forall t>2b\mu$,

$\displaystyle\sum_{i=1}^{N}U_{i}\leq NU^{*}+t.$

Proof. Consider the partition as in (6). Then, using Corollary 2.7 of [Yu94],
we get $\forall t>2b\mu$,

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{N}(U_{i}-U^{*})\geq t\right)$
$\displaystyle\leq$
$\displaystyle\mathbb{P}\left(\sum_{i=1}^{\mu}\sum_{j=1}^{a}(U_{i}-U^{*})\geq
t-2b\mu\right)$ $\displaystyle\leq$
$\displaystyle\mathbb{P}\left(\sum_{i=1}^{\mu}\sum_{j=1}^{a}(\tilde{U}_{(a+b)(i-1)+j}-U^{*})\geq
t-2b\mu\right)+2M(\mu-1)\beta(b).$

where $\sum_{j=1}^{a}(\tilde{U}_{(a+b)(i-1)+j}-U^{*})$ is an
$\operatorname*{\texttt{iid}}$ sequence for $i=1,2,\cdots,\mu$. Using bounded
difference inequality,

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{N}(U_{i}-U^{*})\geq t\right)\leq{\rm
exp}\left(-\frac{(t-2b\mu)^{2}}{2\mu a^{2}M^{2}}\right)+2M(\mu-1)\beta(b).$

So with probability at least $1-{\rm exp}\left(-\frac{(t-2b\mu)^{2}}{2\mu
a^{2}M^{2}}\right)-2M(\mu-1)\beta(b)$,

$\displaystyle\sum_{i=1}^{N}U_{i}\leq NU^{*}+t.$

Lemma B.4-B.6 are needed to prove Lemma B.7 which is the main result needed to
prove Proposition B.1.

######  Lemma B.4.

Let $X_{i},i=1,2,\cdots,N$ be a sample from a sequence for which condition (a)
of Assumption 2.1 is true. For every $0<Q_{\cal H}(2\tau)<1$, we have that
with probability at least $1-c_{1}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{2}Q_{\cal
H}(2\tau)^{1+\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}}$, for some
constants $c_{1},c_{2}>0$, there is a subset $S\subset\\{1,2,\cdots,N\\}$ such
that $\left\lvert S\right\rvert\geq N(1-Q_{\cal H}(2\tau))$, and $\forall i\in
S$,

$\displaystyle\left\lvert
X_{i}\right\rvert\leq\frac{2\|X_{i}\|_{L_{2}}}{\sqrt{Q_{\cal H}(2\tau)}}.$
(73)

Proof. Let $\zeta_{i}=\mathbbm{1}\left(\left\lvert
X_{i}\right\rvert\geq\frac{2\|X_{i}\|_{L_{2}}}{\sqrt{Q_{\cal
H}(2\tau)}}\right)$. Then, by Markov’s inequality,

$\mathbb{E}\left[\zeta_{i}\right]=\mathbb{P}\left(\left\lvert
X_{i}\right\rvert\geq\frac{2\|X_{i}\|_{L_{2}}}{\sqrt{Q_{\cal
H}(2\tau)}}\right)\leq Q_{\cal H}(2\tau)/4.$

Then using Lemma B.3, we have with probability at least $1-{\rm
exp}\left(-\frac{(t-2b\mu)^{2}}{2\mu a^{2}}\right)-2(\mu-1)\beta(b)$,

$\displaystyle\sum_{i=1}^{N}\zeta_{i}\leq\frac{NQ_{\cal H}(2\tau)}{4}+t.$

Now, setting

$\displaystyle t=\frac{3NQ_{\cal H}(2\tau)}{4}\quad a=\frac{(4-Q_{\cal
H}(2\tau))N^{\frac{1}{1+\eta_{1}}}}{c^{\frac{1}{\eta_{1}}}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}}\quad b=\frac{Q_{\cal
H}(2\tau)^{\frac{1}{\eta_{1}}}N^{\frac{1}{1+\eta_{1}}}}{c^{\frac{1}{\eta_{1}}}}\quad\mu=\frac{N^{\frac{\eta_{1}}{1+\eta_{1}}}c^{\frac{1}{\eta_{1}}}Q_{\cal
H}(2\tau)^{\frac{\eta_{1}-1}{\eta_{1}}}}{4},$ (74)

we have $\sum_{i=1}^{N}\zeta_{i}\leq NQ_{\cal H}(2\tau)$, with probability at
least

$\displaystyle 1-c_{1}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{2}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}}.$

######  Lemma B.5.

Let $X_{i},i=1,2,\cdots,N$ be a sample from a sequence for which condition (a)
and (b) of Assumption 2.1 is true. Then with probability at least with

$1-c_{1}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{2}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}},$

there is a subset $S\subset\\{1,2,\cdots,N\\}$ such that $\left\lvert
S\right\rvert\geq 3NQ_{\cal H}(2\tau)/4$, and $\forall i\in S$, $\left\lvert
X_{i}\right\rvert\geq 2\tau\|X_{i}\|_{L_{2}}$.

Proof. Let $\zeta_{i}=\mathbbm{1}\left(\left\lvert X_{i}\right\rvert\geq
2\tau\|X_{i}\|_{L_{2}}\right)$. Using condition (b) of Assumption 2.1, we have
$\mathbb{E}\left[\zeta_{i}\right]>Q_{\cal H}(2\tau)$. Then using Lemma B.3,
with probability at least

$1-c_{1}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{2}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}},$

we have

$\displaystyle 3NQ_{\cal H}(2\tau)/4\leq\sum_{i=1}^{N}\zeta_{i}\leq
5N\mathbb{E}\left[\zeta_{i}\right]/4.$

######  Lemma B.6.

Let $X_{i},i=1,2,\cdots,N$ be a sample from a sequence for which conditions
(a) and (b) of Assumption 2.1 is true. Then with probability at least with

$1-c_{1}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{2}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}},$

there is a subset $S\subset\\{1,2,\cdots,N\\}$ such that $\left\lvert
S\right\rvert\geq NQ_{\cal H}(2\tau)/2$, and $\forall i\in S$,

$\displaystyle 2\tau\|X_{i}\|_{L_{2}}\leq\left\lvert
X_{i}\right\rvert\leq\frac{2\|X_{i}\|_{L_{2}}}{\sqrt{Q_{\cal H}(2\tau)}}.$

Proof. The proof is immediate from Lemma B.4, and Lemma B.5.

######  Lemma B.7.

Let ${\cal H}$ be a class of function which is star-shaped around $0$ and
satisfies condition (b) of Assumption 2.1. If $\zeta_{1}\sim 2\tau Q_{\cal
H}(2\tau)^{3/2}$, $\zeta_{2}\sim 2\tau Q_{\cal H}(2\tau)$, and
$r=\|h\|_{L_{2}}>\omega_{Q}(\zeta_{1},\zeta_{2})$, there is a set
$V_{r}\subset{\cal H}\cap rS(L_{2})$ such that there is an event $\mathcal{A}$
with probability at least $1-c_{6}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{7}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}}$ we have:

  1. 1.

$\displaystyle\left\lvert V_{r}\right\rvert\leq{\rm exp}(c_{2}^{\prime}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}/2),$ (75)

where $c_{2}^{\prime}\leq 1/1000$

  2. 2.

For every $v\in V_{r}$ there is a subset $S_{v}\subset\\{1,2,\cdots,N\\}$ such
that $|S_{v}|\geq Q_{\cal H}(2\tau)N/2$, and for every $i\in S_{v}$,

$\displaystyle 2\tau r\leq\left\lvert
v(X_{i})\right\rvert\leq\frac{c_{3}r}{\sqrt{Q_{\cal H}(2\tau)}}.$ (76)

  3. 3.

For every $h\in{\cal H}\cap rS(L_{2})$ there is some $v\in V_{r}$, and a
subset $K_{h}\subset S_{v}$, containing at least $3/4$ of the coordinates of
$S_{v}$, and for every $k\in K_{h}$,

$\displaystyle\tau\|h\|_{L_{2}}\leq\left\lvert h(X_{k})\right\rvert\leq
c_{9}\left(2\tau+\frac{1}{\sqrt{Q_{\cal H}(2\tau)}}\right)\|h\|_{L_{2}},$ (77)

and $h(X_{k})$ and $v(X_{k})$ have the same sign.

Proof. Let $r=\|h\|_{L_{2}}>\omega_{Q}(\zeta_{1},\zeta_{2})$. Let
$V_{r}\subset H\cap rS(L_{2})$ be a maximal $\rho$-separated set such that

$\left\lvert V_{r}\right\rvert\leq{\rm exp}(c_{2}^{\prime}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}/2)$

where $c_{2}^{\prime}=\min(c_{2},1/500)$. Applying Lemma B.6 on all the
elements of $V_{r}$, using union bound we obtain that with probability at
least

$1-c_{1}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{2}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}/2},$

for every $v\in V_{r}$ there is a subset $S_{v}$ such that $\left\lvert
S_{v}\right\rvert\geq NQ_{\cal H}(2\tau)/2$ and for all $i\in S_{v}$, we have

$\displaystyle 2\tau\|v(X_{i})\|_{L_{2}}\leq\left\lvert
v(X_{i})\right\rvert\leq\frac{c_{3}\|v(X_{i})\|_{L_{2}}}{\sqrt{Q_{\cal
H}(2\tau)}}.$ (78)

Since we have assumed $r>\omega_{1}(\zeta_{1})$, from Sudakov’s inequality we
have,

$\displaystyle\rho\leq c_{4}\frac{\sqrt{2}\mathbb{E}\left[\|G\|_{{\cal H}\cap
rS(L_{2})}\right]}{\sqrt{c_{2}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}}}\leq\frac{c_{5}\zeta_{1}r}{\sqrt{Q_{\cal
H}(2\tau)}},$ (79)

where $c_{5}=\sqrt{2}c_{4}/\sqrt{c_{2}}$. For all $h\in{\cal H}\cap
rS(L_{2})$, let $h_{v}\in V_{r}$ so that $\|h-h_{v}\|_{L_{2}}\leq\rho$. Now
let $\delta_{h}=\mathbbm{1}_{\left(\left\lvert h-h_{v}\right\rvert>\tau
r\right)}$ and put

$\displaystyle\Delta_{r}=\left\\{\delta_{h}:h\in{\cal H}\cap
rS(L_{2})\right\\}.$ (80)

Define a function $\psi_{1}(t)=\max(\min(t/(\tau r),1),0)$. Observe that
$\delta_{h}(X)\leq\psi_{1}\left(\left\lvert h-h_{v}\right\rvert(X)\right)$.
Now we want to show that the number of points where $\left\lvert
h-h_{v}\right\rvert>\tau r$ is small.

$\displaystyle\mathbb{E}\left[\sup_{\delta_{h}\in\Delta_{r}}\frac{1}{N}\sum_{i=1}^{N}\delta_{h}(X_{i})\right]$
$\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\sup_{h\in{\cal H}\cap
rS(L_{2})}\frac{1}{N}\sum_{i=1}^{N}\psi_{1}(\left\lvert
h-h_{v}\right\rvert(X_{i}))\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\sup_{h\in{\cal H}\cap
rS(L_{2})}\frac{1}{N}\sum_{i=1}^{N}\left(\psi_{1}(\left\lvert
h-h_{v}\right\rvert(X_{i}))-\mathbb{E}\left[\psi_{1}(\left\lvert
h-h_{v}\right\rvert(X)\right]\right)\right]+\mathbb{E}\left[\sup_{h\in{\cal
H}\cap rS(L_{2})}\mathbb{E}\left[\psi_{1}(\left\lvert
h-h_{v}\right\rvert(X)\right]\right],$

where $X\sim\pi$. Consider the partition introduced in (6). Then,

$\displaystyle\mathbb{E}\left[\sup_{\delta_{h}\in\Delta_{r}}\frac{1}{N}\sum_{i=1}^{N}\delta_{h}(X_{i})\right]$
$\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\sup_{h\in{\cal H}\cap
rS(L_{2})}\frac{1}{N}\sum_{i=1}^{\mu}\sum_{j=1}^{a}\left(\psi_{1}(\left\lvert
h-h_{v}\right\rvert(X_{(a+b)(i-1)+j}))-\mathbb{E}\left[\psi_{1}(\left\lvert
h-h_{v}\right\rvert(X)\right]\right)\right]$
$\displaystyle+\frac{2b\mu}{N}+\frac{1}{\tau r}\mathbb{E}\left[\sup_{h\in{\cal
H}\cap rS(L_{2})}\mathbb{E}\left[\left\lvert
h-h_{v}\right\rvert(X)\right]\right]$ $\displaystyle\leq$
$\displaystyle\frac{\mu}{N}\sum_{j=1}^{a}\mathbb{E}\left[\sup_{h\in{\cal
H}\cap rS(L_{2})}\frac{1}{\mu}\sum_{i=1}^{\mu}\left(\psi_{1}(\left\lvert
h-h_{v}\right\rvert(X_{(a+b)(i-1)+j}))-\mathbb{E}\left[\psi_{1}(\left\lvert
h-h_{v}\right\rvert(X)\right]\right)\right]$
$\displaystyle+\frac{2b\mu}{N}+\frac{\rho}{\tau r}$ $\displaystyle\leq$
$\displaystyle\frac{\mu}{N}\sum_{j=1}^{a}\mathbb{E}\left[\sup_{h\in{\cal
H}\cap rS(L_{2})}\frac{1}{\mu}\sum_{i=1}^{\mu}\left(\psi_{1}(\left\lvert
h-h_{v}\right\rvert(\tilde{X}_{(a+b)(i-1)+j}))-\mathbb{E}\left[\psi_{1}(\left\lvert
h-h_{v}\right\rvert(X)\right]\right)\right]$
$\displaystyle+2(\mu-1)\beta(a+b)+\frac{2b\mu}{N}+\frac{\rho}{\tau r}.$

Now using symmetrization, we get

$\displaystyle\mathbb{E}\left[\sup_{\delta_{h}\in\Delta_{r}}\frac{1}{N}\sum_{i=1}^{N}\delta_{h}(X_{i})\right]$
$\displaystyle\leq\frac{\mu}{N}\sum_{j=1}^{a}\mathbb{E}\left[\sup_{h\in{\cal
H}\cap rS(L_{2})}\frac{1}{\mu}\sum_{i=1}^{\mu}Q_{\cal
H}(2\tau)_{i}\psi_{1}(\left\lvert
h-h_{v}\right\rvert(\tilde{X}_{(a+b)(i-1)+j}))\right]$
$\displaystyle~{}~{}~{}+2(\mu-1)\beta(a+b)+\frac{2b\mu}{N}+\frac{\rho}{\tau
r}.$

Since $\psi_{1}(\left\lvert\cdot\right\rvert)$ is a $1/(\tau r)$-Lipschitz
continuous mapping, using properties of Rademacher complexity we have

$\displaystyle\mathbb{E}\left[\sup_{h\in{\cal H}\cap
rS(L_{2})}\frac{1}{\mu}\sum_{i=1}^{\mu}Q_{\cal
H}(2\tau)_{i}\psi_{1}(\left\lvert
h-h_{v}\right\rvert(\tilde{X}_{(a+b)(i-1)+j}))\right]$
$\displaystyle\leq\frac{1}{\tau r}\mathbb{E}\left[\sup_{h\in{\cal H}\cap
rS(L_{2})}\frac{1}{\mu}\sum_{i=1}^{\mu}Q_{\cal
H}(2\tau)_{i}(h-h_{v})(\tilde{X}_{(a+b)(i-1)+j}))\right].$

Since we assumed $r>\omega_{2}(\zeta_{2})$, and using (79) we have,

$\displaystyle\mathbb{E}\left[\sup_{\delta_{h}\in\Delta_{r}}\frac{1}{N}\sum_{i=1}^{N}\delta_{h}(X_{i})\right]\leq\frac{a\zeta_{2}\mu}{N\tau}+2(\mu-1)\beta(a+b)+\frac{2b\mu}{N}+\frac{c_{5}\zeta_{1}}{\tau\sqrt{Q_{\cal
H}(2\tau)}}.$

Choosing

$\displaystyle\zeta_{1}\sim 2\tau Q_{\cal
H}(2\tau)^{\frac{3}{2}}\quad\zeta_{2}\sim 2\tau Q_{\cal H}(2\tau)$
$\displaystyle\quad a\sim\frac{(4-Q_{\cal
H}(2\tau))N^{1/(1+\eta_{1})}}{c^{\frac{1}{\eta_{1}}}}$ (81) $\displaystyle
b\sim\frac{Q_{\cal
H}(2\tau)N^{1/(1+\eta_{1})}}{c^{\frac{1}{\eta_{1}}}}~{}~{}~{}$
$\displaystyle\text{and}~{}~{}\mu\sim\frac{N^{\eta_{1}/(1+\eta_{1})}c^{\frac{1}{\eta_{1}}}}{4},$
(82)

we have,

$\displaystyle\mathbb{E}\left[\sup_{\delta_{h}\in\Delta_{r}}\frac{1}{N}\sum_{i=1}^{N}\delta_{h}(X_{i})\right]\leq\frac{Q_{\cal
H}(2\tau)}{32}.$

Now we use Lemma B.3, with the following choice

$\displaystyle t=\frac{NQ_{\cal H}(2\tau)}{32}\quad a=\frac{(4-\frac{Q_{\cal
H}(2\tau)}{16})N^{1/(1+\eta_{1})}}{c^{\frac{1}{\eta_{1}}}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}}\quad b=\frac{Q_{\cal
H}(2\tau)^{\frac{1}{\eta_{1}}}N^{1/(1+\eta_{1})}}{32c^{\frac{1}{\eta_{1}}}}\quad\mu=\frac{N^{\eta_{1}/(1+\eta_{1})}c^{\frac{1}{\eta_{1}}}Q_{\cal
H}(2\tau)^{\frac{\eta_{1}-1}{\eta_{1}}}}{4}.$

With probability at least $1-c_{6}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{7}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}}$ we have,

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\sup_{\delta_{h}\in\Delta_{r}}\delta_{h}(X_{i})\leq\mathbb{E}\left[\frac{1}{N}\sum_{i=1}^{N}\sup_{\delta_{h}\in\Delta_{r}}\delta_{h}(X_{i})\right]+\frac{t}{N}\leq\frac{Q_{\cal
H}(2\tau)}{16}.$

Then $\forall h\in{\cal H}\cap rS(L_{2})$,

$\displaystyle\left\lvert\\{i:\left\lvert h-h_{v}\right\rvert(X_{i})\leq\tau
r\\}\right\rvert\geq\left(1-\frac{Q_{\cal H}(2\tau)}{16}\right)N.$ (83)

Recall that $h_{v}\in V_{r}$, and $|S_{h_{v}}|\geq NQ_{\cal H}(2\tau)/2$. Let

$\displaystyle K_{h}=\\{k:\left\lvert h-h_{v}\right\rvert(X_{k})\leq\tau
r\\}\cap S_{h_{v}}.$ (84)

Then $|K_{h}|\geq 3NQ_{\cal H}(2\tau)/8\geq NQ_{\cal H}(2\tau)/4$. Also,
$\forall k\in K_{h}$,

$\displaystyle|h(X_{k})|\geq|h_{v}(X_{k})|-|(h-h_{v})(X_{k})|\geq 2\tau r-\tau
r=\tau r.$ (85)

This also implies that $h(X_{k})$ and $h_{v}(X_{k})$ have same signs.
Similarly, using (78) we get

$\displaystyle|h(X_{k})|\leq|h_{v}(X_{k})|+|(h-h_{v})(X_{k})|\leq
c_{9}(2\tau+\frac{1}{\sqrt{Q_{\cal H}(2\tau)}})\|h\|_{L_{2}}.$ (86)

Combining (85) and (86) we have (77). This also implies that $h(X_{k})$ and
$v(X_{k})$ have the same sign.

######  Lemma B.8 ([Men18, Lemma 4.8]).

Let $1\leq k\leq m/40$ and set $\mathscr{D}\subset\\{-1,0,1\\}^{m}$ of
cardinality at most ${\rm exp}(k)$. For every
$d=(d(i))_{i=1}^{m}\in\mathscr{D}$ put $S_{d}=\\{i:d(i)\neq 0\\}$ and assume
that $|S_{d}|\geq 40k$. If $\\{\epsilon_{i}\\}_{i=1}^{m}$ are independent,
symmetric $\\{-1,1\\}$-valued random variables, then with probability at least
$1-2{\rm exp}(-k)$,

$\displaystyle\inf_{d\in\mathscr{D}}\left\lvert\\{i\in
S_{d}:sgn(d(i))=\epsilon_{i}\\}\right\rvert\geq k/3.$

######  Lemma B.9.

Conditioned on the event $\mathcal{A}$ as mentioned in Lemma B.7, with
probability at least $1-2{\rm exp}(-c_{2}Q_{\cal H}(2\tau)N)$ we have: for
every $h\in{\cal H}_{f^{*}}\coloneqq{\cal F}-f^{*}$ with $\|h\|_{L_{2}}\geq
r$, there is a subset $\mathcal{S}_{1,h}\subset\\{1,2,\cdots,N\\}$ such that
$\left\lvert\mathcal{S}_{1,h}\right\rvert\geq Q_{\cal H}(2\tau)N/24$. and for
every $i\in\mathcal{S}_{1,h}$,

$\displaystyle\tau\|h\|_{L_{2}}\leq\left\lvert h(X_{i})\right\rvert\leq
c_{9}\left(2\tau+\frac{1}{\sqrt{Q_{\cal H}(2\tau)}}\right)\|h\|_{L_{2}},\qquad
sgn(h(X_{i}))=\epsilon_{i},$ (87)

where $\\{\epsilon_{i}\\}_{i=1}^{N}$ are independent, symmetric
$\\{-1,1\\}$-valued random variables.

Proof. For a $h\in{\cal H}$, let $\|h\|_{L_{2}}=r$ and let $h_{v}$ be as in
Lemma B.7. Recall from (77), that there is a subset $K_{h}\subset S_{h_{v}}$
containing at least $3/4$ of the coordinates of $S_{h_{v}}$ for which,

$\displaystyle\tau r\leq\left\lvert h(X_{j})\right\rvert\leq
c_{9}\left(2\tau+\frac{1}{\sqrt{Q_{\cal H}(2\tau)}}\right)r,$

and $h(X_{j})$ and $h_{v}(X_{j})$ have the same sign. Define

$\displaystyle
d_{h_{v}}=\\{sgn(h_{v}(X_{i}))\mathbbm{1}_{S_{h_{v}}}(X_{i})\\}_{i=1}^{N},\qquad\mathcal{D}=\\{d_{h_{v}}:h_{v}\in
V_{r}\\}.$

Using Lemma B.8, on the set $\mathcal{D}=\\{d_{h_{v}}:d_{h_{v}}\in V_{r}\\}$
for $k=NQ_{\cal H}(2\tau)/1000$, and observing that every
$d_{h_{v}}\in\mathcal{D}$, $\left\lvert\\{i:d_{h_{v}}(i)\neq
0\\}\right\rvert\geq NQ_{\cal H}(2\tau)/2\geq 40k$ (recall that
$|S_{h_{v}}|\geq NQ_{\cal H}(2\tau)/2$), we get with probability at least
$1-2{\rm exp}(-c_{2}Q_{\cal H}(2\tau)N)$, for every ${h_{v}}\in V_{r}$,
$d_{h_{v}}(i)=\epsilon_{i}$ on at least $1/3$ of the coordinates of
$S_{h_{v}}$. Then it follows that on at least $1/12$ of the coordinates of
$S_{h_{v}}$, $h(X_{j})=\epsilon_{j}$. Since ${\cal H}_{f^{*}}$ is assumed to
be star-shaped the same result holds when $\|h\|_{L_{2}}\geq r$.

######  Proposition B.1.

With probability at least $1-c_{9}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{10}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}}$, for every $f\in{\cal F}$ which satisfies
$\|f-f^{*}\|_{L_{2}}\geq 2\omega_{Q}$ we have

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\ell^{\prime\prime}(\widetilde{\xi}_{i})(f-f^{*})^{2}(X_{i})\geq
c_{16}Q_{\cal H}(2\tau)\rho(0,t_{0})\tau^{2}\|f-f^{*}\|_{L_{2}}^{2}.$ (88)

where $t_{0}=c_{11}(2\tau+1/\sqrt{Q_{\cal
H}(2\tau)})\left(\|\xi\|_{L_{2}}+\|f-f^{*}\|_{L_{2}}\right)$.

Proof. [Proof of Proposition B.1] Recall the decomposition of $P_{N}L_{f}$
(1). For every $(X,Y)$ the midpoint $\tilde{\xi}$ belongs to the interval with
end points $-\xi$ and $(f-f^{*})(X)-\xi$ where $f\in{\cal F}$. So,

$\displaystyle|\tilde{\xi}_{i}|\leq|\xi_{i}|+\left\lvert(f-f^{*})(X_{i})\right\rvert.$

Let $\|f-f^{*}\|_{L_{2}}>2\omega_{Q}$. Now from Lemma B.9, with probability at
least

$1-c_{9}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{10}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}},$

we have a subset $\mathcal{S}_{1,h}\subset\\{1,2,\cdots,N\\}$ such that
$\left\lvert\mathcal{S}_{1,h}\right\rvert\geq Q_{\cal H}(2\tau)N/24$, and for
every $i\in\mathcal{S}_{1,h}$,

$\displaystyle\left\lvert(f-f^{*})(X_{i})\right\rvert\leq
c_{9}(2\tau+1/\sqrt{Q_{\cal H}(2\tau)})\|f-f^{*}\|_{L_{2}}.$

Using Markov’s inequality,

$\displaystyle\mathbb{P}(|\xi_{i}|>10\|\xi\|_{L_{2}}/\sqrt{Q_{\cal
H}(2\tau)})\leq\frac{Q_{\cal H}(2\tau).}{100}$

Now taking
$U_{i}=\mathbbm{1}\left(|\xi_{i}|\leq\frac{c_{9}\|\xi\|_{L_{2}}}{\sqrt{Q_{\cal
H}(2\tau)}}\right)$, and using Lemma B.3, and choosing parameters as in (74)
we get, with probability at least $1-c_{1}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{2}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}}$,

$\displaystyle\left\lvert\\{i:|\xi_{i}|\leq\frac{c_{9}\|\xi\|_{L_{2}}}{\sqrt{Q_{\cal
H}(2\tau)}}\\}\right\rvert\geq N(1-Q_{\cal H}(2\tau)/50).$

This implies that with probability at least $1-c_{16}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{17}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}}$ we have,

$\displaystyle|\tilde{\xi}_{i}|\leq c_{11}(2\tau+1/\sqrt{Q_{\cal
H}(2\tau)})\left(\|\xi\|_{L_{2}}+\|f-f^{*}\|_{L_{2}}\right).$

Set $t_{0}=c_{11}(2\tau+1/\sqrt{Q_{\cal
H}(2\tau)})\left(\|\xi\|_{L_{2}}+\|f-f^{*}\|_{L_{2}}\right)$. Using Lemma B.9,
with probability at least $1-c_{9}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{10}Q_{\cal
H}(2\tau)N^{\eta_{1}/(1+\eta_{1})}}$,

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\ell^{\prime\prime}(\widetilde{\xi}_{i})(f-f^{*})^{2}(X_{i})\geq
c_{16}Q_{\cal H}(2\tau)\rho(0,t_{0})\tau^{2}\|f-f^{*}\|_{L_{2}}^{2}.$ (89)

Using Proposition B.1, and proving the two-sided bounds for the second term on
the RHS of (72) in (94) and (95), we have Proposition B.2.

######  Proposition B.2.

Consider ERM with loss functions that satisfy Assumption 3.2. For
$\tau_{0}<c_{2}Q_{{\cal F}-{\cal F}}(2\tau)\rho(0,t_{0})\tau^{2}$,
$t_{0}=\mathcal{O}((2\tau+1/\sqrt{Q_{{\cal
H}}(2\tau)})(\|\xi\|_{L_{2}}+\|f-f^{*}\|_{L_{2}}))$, setting
$\mu=N^{\eta_{1}/(1+\eta_{1})}$, for some constants $c,c^{\prime}>0$, we have,
for any $N\geq 4$, the following:

  1. 1.

Under conditions (a), (b), (c)-(i), and (d) of Assumption 2.1, for $\
0<\iota<\frac{1}{4}$,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{1}{4}+\iota},2\omega_{Q}({\cal
F}-{\cal F},N,Q_{\cal H}(2\tau)^{3/2},Q_{\cal H}(2\tau))\right\\},$ (90)

with probability at least (for $V$ is defined in (8) and some positive
$c_{9},c_{10},\widetilde{C}_{3}$)

$\displaystyle 1-c_{9}Q_{{\cal
H}}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{10}Q_{{\cal
H}}(2\tau)^{1+\frac{1}{\eta_{1}}}N^{\frac{\eta_{1}}{1+\eta_{1}}}}-\widetilde{C}_{3}N{\rm
exp}\left(-(N^{\frac{1}{2}+2\iota}\tau_{0})^{\eta}/C_{1}\right).$

  2. 2.

Under conditions (a), (b), and (c)-(ii) of Assumption 2.1, for $\
0<\iota<(1-1/\eta_{2})/4$,

$\displaystyle\|\hat{f}-f^{*}\|_{L_{2}}\leq\max\left\\{N^{-\frac{(1-1/\eta_{2})}{4}+\iota},2\omega_{Q}({\cal
F}-{\cal F},N,Q_{\cal H}(2\tau)^{3/2},Q_{\cal H}(2\tau))\right\\},$ (91)

with probability at least (for constants $c_{9},c_{10},\widetilde{C}_{4}>0$)

$\displaystyle 1-c_{9}Q_{{\cal
H}}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{10}Q_{{\cal
H}}(2\tau)^{1+\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}}-\widetilde{C}_{4}\tau_{0}^{-\frac{2\eta_{2}}{1+\eta_{2}}}N^{-\frac{4\iota\eta_{2}}{1+\eta_{2}}}.$
(92)

Proof. [Proof of Proposition B.2] We first prove part 1. We will denote the
class ${\cal F}-f^{*}$ by ${\cal H}$. From Proposition B.1 it follows that for
every $f\in{\cal F}$ which satisfies $\|f-f^{*}\|_{L_{2}}\geq 2\omega_{Q}$
with probability at least

$\mathscr{P}_{1,c}=1-c_{9}Q_{\cal
H}(2\tau)^{1-\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}e^{-c_{10}Q_{\cal
H}(2\tau)^{1+\frac{1}{\eta_{1}}}N^{\eta_{1}/(1+\eta_{1})}},$

we have

$\displaystyle\frac{1}{N}\sum_{i=1}^{N}\ell^{\prime\prime}(\widetilde{\xi}_{i})(f-f^{*})^{2}(X_{i})\geq
c_{16}Q_{\cal H}(2\tau)\rho(0,t_{2})\tau^{2}\|f-f^{*}\|_{L_{2}}^{2}.$

So, with probability at least $\mathscr{P}_{1,c}$, for every $f\in{\cal F}$
that satisfies $\|f-f^{*}\|_{L_{2}}\geq 2\omega_{Q}$,

$\displaystyle
P_{N}\mathcal{L}_{f}\geq\left(\frac{1}{16N}\sum_{i=1}^{N}l^{\prime}(\xi_{i})(f-f^{*})(X_{i})-\mathbb{E}\left[l^{\prime}(\xi)(f-f^{*})\right]\right)+c_{16}Q_{\cal
H}(2\tau)\rho(0,t_{2})\tau^{2}\|f-f^{*}\|_{L_{2}}^{2}.$ (93)

When $\|f-f^{*}\|_{L_{2}}\geq\mathscr{A}(N)>2(N\tau_{0})^{-1/2}$, we have
$\log(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})\leq
2(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{(1-\eta)/2}/(1-\eta)$. Under Conditions
(1), (3), and (4) of Assumption 2.1, using Lemma 2.1, we get

$\displaystyle{\mathbb{P}}\left(\left\lvert\frac{1}{N}\sum_{i=1}^{N}l^{\prime}(\xi_{i})(f-f^{*})(X_{i})-\mathbb{E}\left[l^{\prime}(\xi)(f-f^{*})\right]\right\rvert\geq\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}\right)$
$\displaystyle\leq$ $\displaystyle N{\rm
exp}\left(-\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta}}{C_{1}}\right)+{\rm
exp}\left(-\frac{N^{2}\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{2}(1+NV)}\right)$
$\displaystyle+$ $\displaystyle{\rm
exp}\left(-\frac{N\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{3}}{\rm
exp}\left(\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta(1-\eta)}}{C_{4}(\log(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2}))^{\eta}}\right)\right)$
$\displaystyle\leq$ $\displaystyle N{\rm
exp}\left(-\frac{(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\eta}}{C_{1}}\right)+{\rm
exp}\left(-\frac{N^{2}\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{2}(1+NV)}\right)$
$\displaystyle+$ $\displaystyle{\rm
exp}\left(-\frac{N\tau_{0}^{2}\|f-f^{*}\|_{L_{2}}^{4}}{C_{3}}{\rm
exp}\left(\frac{(1-\eta)^{\eta}(N\tau_{0}\|f-f^{*}\|_{L_{2}}^{2})^{\frac{{\eta(1-\eta)}}{2}}}{C_{4}2^{\eta}}\right)\right)$
$\displaystyle\leq$ $\displaystyle N{\rm
exp}\left(-\frac{(N\tau_{0}\mathscr{A}(N)^{2})^{\eta}}{C_{1}}\right)+{\rm
exp}\left(-\frac{N^{2}\tau_{0}^{2}\mathscr{A}(N)^{4}}{C_{2}(1+NV)}\right)$
$\displaystyle+$ $\displaystyle{\rm
exp}\left(-\frac{N\tau_{0}^{2}\mathscr{A}(N)^{4}}{C_{3}}{\rm
exp}\left(\frac{(1-\eta)^{\eta}(N\tau_{0}\mathscr{A}(N)^{2})^{\frac{{\eta(1-\eta)}}{2}}}{C_{4}2^{\eta}}\right)\right)\equiv\mathscr{P}_{2,c},$
(94)

where

$V\leq\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{2}\right]+4\sum_{i\geq
0}\mathbb{E}\left[B_{i}\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{2}\right],$

$\\{B_{i}\\}$ is some sequence such that $B_{i}\in[0,1]$ and
$\mathbb{E}\left[B_{i}\right]\leq\beta(i)$, and $C_{1},C_{2},C_{3}$ are
constants which depend on $c,\eta,\eta_{1},\eta_{2}$. Observe that,

$\displaystyle V\leq$
$\displaystyle\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{2}\right]+4\sum_{i\geq
0}\mathbb{E}\left[B_{i}\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{2}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{2}\right]+4\sum_{i\geq
0}\sqrt{\mathbb{E}\left[B_{i}^{2}\right]\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{4}\right]}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{2}\right]+4\sqrt{\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{4}\right]}\sum_{i\geq
0}\sqrt{\mathbb{E}\left[B_{i}\right]}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{2}\right]+4\sqrt{\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{4}\right]}\sum_{i\geq
0}\sqrt{\beta(i)}$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{2}\right]+4\sqrt{\mathbb{E}\left[\left(\ell^{\prime}(\xi_{1})(f-f^{*})(X_{1})\right)^{4}\right]}\sum_{i\geq
0}{\rm exp}(-ci^{\eta_{1}}/2)$ $\displaystyle\leq$ $\displaystyle
2^{\frac{2}{\eta_{2}}}+C4^{1+\frac{2}{\eta_{2}}}.$

Combining (93), and (94), with probability at least
$\mathscr{P}_{1,c}-\mathscr{P}_{2,c}$, for every $f\in{\cal F}$ that satisfies
$\|f-f^{*}\|_{L_{2}}\geq\max(2\omega_{Q},\mathscr{A}(N))$, we get