# Robust nonparametric regression based on deep ReLU neural networks

Juntong CHEN  Department of Mathematics (DMATH), University of Luxembourg
Maison du nombre 6 avenue de la Fonte L-4364 Esch-sur-Alzette Grand Duchy of
Luxembourg<EMAIL_ADDRESS>
(Date: August 28, 2024)

###### Abstract.

In this paper, we consider robust nonparametric regression using deep neural
networks with ReLU activation function. While several existing theoretically
justified methods are geared towards robustness against identical heavy-tailed
noise distributions, the rise of adversarial attacks has emphasized the
importance of safeguarding estimation procedures against systematic
contamination. We approach this statistical issue by shifting our focus
towards estimating conditional distributions. To address it robustly, we
introduce a novel estimation procedure based on $\ell$-estimation. Under a
mild model assumption, we establish general non-asymptotic risk bounds for the
resulting estimators, showcasing their robustness against contamination,
outliers, and model misspecification. We then delve into the application of
our approach using deep ReLU neural networks. When the model is well-specified
and the regression function belongs to an $\alpha$-Hölder class, employing
$\ell$-type estimation on suitable networks enables the resulting estimators
to achieve the minimax optimal rate of convergence. Additionally, we
demonstrate that deep $\ell$-type estimators can circumvent the curse of
dimensionality by assuming the regression function closely resembles the
composition of several Hölder functions. To attain this, new deep fully-
connected ReLU neural networks have been designed to approximate this
composition class. This approximation result can be of independent interest.

###### Key words and phrases:

Nonparametric regression, robust estimation, deep neural networks,
circumventing the curse of dimensionality, supremum of an empirical process

###### 2010 Mathematics Subject Classification:

Primary 62G35, 62G05; Secondary 68T01

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under grant agreement No 811017

##  1\. Introduction

A standard nonparametric regression model takes the form

$Y_{i}=f^{\star}(W_{i})+\sigma\varepsilon_{i},\quad i=1,\ldots,n,$

where $Y_{1},\ldots,Y_{n}$ are real-valued observations, $W_{1},\ldots,W_{n}$
are fixed or random design points in ${\mathscr{W}}$ (typically
${\mathscr{W}}\subset{\mathbb{R}}^{d}$ for some positive integer $d$),
$\sigma$ is a known positive constant,
$\varepsilon_{1},\ldots,\varepsilon_{n}$ are unobserved i.i.d. standard real-
valued Gaussian random variables which are independent of
$W_{1},\ldots,W_{n}$, and $f^{\star}:{\mathscr{W}}\rightarrow{\mathbb{R}}$ is
an unknown regression function that we want to estimate.

A substantial body of literature addresses this problem through the
minimization of empirical least squares loss functions. By integrating such a
classical estimation approach with various approximation models, several
methods have been developed and investigated. These include kernel regression
(e.g., Nadaraya, (1964) and Watson, (1964)), local polynomial regression
(e.g., Fan, (1992, 1993)), spline-based regression (e.g., Wahba, (1990) and
Friedman, (1991)), and wavelet-based regression (e.g., Donoho et al., (1995)
and Donoho and Johnstone, (1998)), among others. In-depth discussions on
different methods and theories related to nonparametric regression can also be
found in books such as Györfi et al., (2002) and Tsybakov, (2009).
Particularly, when $f^{\star}:\left[{0,1}\right]^{d}\rightarrow{\mathbb{R}}$
is of $\alpha$-smoothness, Stone, (1982) demonstrated that the minimax optimal
convergence rate is of the order $n^{-2\alpha/(2\alpha+d)}$ with respect to
some squared ${\mathbb{L}}_{2}$-loss. As the value of $d$ becomes large, the
convergence rate can become extremely slow, which is a well-known phenomenon
called the curse of dimensionality. One possible way to overcome this
difficulty is to make additional structural assumptions on the regression
function $f^{\star}$ namely to assume that the unknown function $f^{\star}$ is
of the form $f_{1}\circ f_{2}$ where $f_{1}$ and $f_{2}$ have some specific
structures (e.g., Stone, (1985), Horowitz and Mammen, (2007) and Baraud and
Birgé, (2014)). For instance, under the generalized additive structure of
$f^{\star}$, Horowitz and Mammen, (2007) showed that, one can estimate the
regression function $f^{\star}$ with rate $n^{-2\alpha/(2\alpha+1)}$ which is
independent of the dimension $d$.

Recently, estimation based on neural networks has demonstrated remarkable
success in both experimental and practical domains. Inspiring work has been
carried out to systematically analyze the theoretical properties of least
squares estimators implemented by various structured neural networks,
particularly those employing a ReLU activation function. We mention the work
of Schmidt-Hieber, (2020), Kohler and Langer, (2021), Suzuki and Nitanda,
(2021) and Jiao et al., (2023), among others. Based on the established
approximation results, these studies have revealed that least squares
estimators implemented using appropriate neural network architectures achieve
the same minimax convergence rate as that obtained in Stone, (1982) when
considering a regression function $f^{\star}$ with $\alpha$-smoothness.
However, these findings also indicate that without further assumptions on the
underlying model, nonparametric regression using deep neural networks is not
immune to the curse of dimensionality. Much effort has been devoted to
mitigating this issue through network-based estimation approaches (e.g.,
Schmidt-Hieber, (2019), Chen et al., (2022) and Nakada and Imaizumi, (2020)
where they assume that the distribution of $W$ is supported on a low-
dimensional manifold, or the covariates exhibit a low intrinsic dimension, and
Bauer and Kohler, (2019), Suzuki, (2019), where structural assumptions are
imposed on $f^{\star}$). In particular, it is worth mentioning that, as shown
in Schmidt-Hieber, (2020), neural networks, especially deep ones, exhibit a
natural advantage in approximating functions with a compositional structure
compared to classical approximation methods.

Given a collection of candidate estimators for $f^{\star}$, most of the
aforementioned approaches derive their estimators by minimizing a least-
squares-based objective function. While possessing several desirable
properties, least squares estimators are highly susceptible to data
contamination and the presence of outliers, which are common scenarios
encountered in practical applications. To address this issue of instability,
several alternative approaches have been proposed in the context of linear
regression, such as Huber regression (Huber, (1973)), Tukey’s biweight
regression (Beaton and Tukey, (1974)) and the least absolute deviation
regression (Bassett and Koenker, (1978)).

In the realm of deep learning, a prevailing characteristic is the presence of
data abundant in quantity but often deficient in quality. As a result,
robustness becomes an essential property to consider when implementing
estimation procedures based on deep neural networks (Barron, (2019)). However,
there has been significantly less research conducted in this field. In
Lederer, (2020), upper bounds for the expected excess risks of a specific
class of estimators were established. These estimators are obtained by
minimizing empirical risk using unbounded, Lipschitz-continuous loss functions
on feedforward neural networks, covering cases such as the least absolute
deviation loss, Huber loss, Cauchy loss, and Tukey’s biweight loss. Jiao et
al., (2023) investigated a similar class of estimators. They relaxed several
assumptions required in Lederer, (2020), which led to the establishment of
their non-asymptotic expected excess risk bounds under milder conditions. They
also considered the approximation error introduced by the ReLU neural network
and demonstrated that the curse of dimensionality can be mitigated for such
class of estimators if the distribution of $W$ is assumed to be supported on
an approximately low-dimensional manifold. Drawing upon the approximation
results established in Schmidt-Hieber, (2020) and Suzuki, (2019), Padilla et
al., (2022) examined the properties of quantile regression using deep ReLU
neural networks. When the underlying quantile function can be represented as a
composition of Hölder functions or when it belongs to a Besov space, they
derived convergence rates for the resulting estimators in terms of the mean
squared error at the design points. All the previously mentioned work that
addresses robust nonparametric regression using deep neural networks assumes
the existence of the regression function $f^{\star}$. The approaches they
considered and analyzed focus on the robustness under the scenarios where
there is a departure from Gaussian distributions to heavy-tailed
distributions. When it comes to the case of adversarial attacks, where the
statistical model is misspecified from a distributional perspective, their
results are unable to provide a theoretical guarantee for the performance of
the resulting estimators.

In this paper, we approach the nonparametric regression problem from a novel
perspective that acknowledges the possibility of misspecification at the
distributional level. We propose a general procedure under mild assumptions to
address this problem in a robust manner and investigate its application to
ReLU neural networks. Specifically, our primary contributions are as follows.

  1. (i)

We consider this estimation problem from the perspective of estimating the
conditional distributions $Q_{i}^{\star}(W_{i})$ of $Y_{i}$ given $W_{i}$. To
handle this statistical issue, we propose an $\ell$-type estimation procedure
based on a development of $\ell$-estimation methodology proposed in Baraud,
(2021). Our approach is based on the presumption that there exists an
underlying function $f^{\star}$ on ${\mathscr{W}}$ belonging to some
collection $\overline{\mathcal{F}}$ such that $Q_{i}^{\star}(W_{i})$ is of the
form $Q_{f^{\star}(W_{i})}\sim{\mathcal{N}}(f^{\star}(W_{i}),\sigma^{2})$ for
all $i\in\\{1,\ldots,n\\}$. However, our method is not confined to this
assumption. In other words, we allow our statistical models to be slightly
misspecified: $Q_{i}^{\star}(W_{i})$ may not be exactly of the form
$Q_{f^{\star}(W_{i})}$ and even if they were, $f^{\star}$ may not belong to
the class $\overline{\mathcal{F}}$.

  2. (ii)

Assuming that $\overline{\mathcal{F}}$ is a VC-subgraph class on
${\mathscr{W}}$, we derive a non-asymptotic risk bound for the resulting
estimators, measured in terms of the total-variation type distance. Building
upon this general result, we offer a comprehensive elucidation of the
robustness of our estimators with regard to model misspecification at the
distributional level. We also provide a quantitative comparison between the
$\ell$-type estimators and another type of robust estimators known as
$\rho$-estimators, which were introduced in Baraud and Chen, (2020).

  3. (iii)

We showcase the application of our $\ell$-type estimation procedure using ReLU
neural network models. In the case of a well-specified model, we derive
uniform risk bounds over Hölder classes for our estimators. By incorporating
the lower bounds that we established, we demonstrate that the resulting
estimators achieve the minimax optimal rate of convergence.

  4. (iv)

We consider the problem of circumventing the curse of dimensionality by
imposing structural assumptions on the underlying regression function
$f^{\star}$. More precisely, we assume the function $f^{\star}$ can be
expressed as a composition of several Hölder functions, following the
consideration in Schmidt-Hieber, (2020). In contrast to using sparsity-based
ReLU neural networks as in Schmidt-Hieber, (2020), we develop new deep fully-
connected ReLU neural networks to approximate composite Hölder functions,
enhancing the informativeness of the architectural design. This approximation
result can be of independent interest. By leveraging the derived approximation
theory, we demonstrate that the $\ell$-type estimators implemented based on
appropriate network models can alleviate the curse of dimensionality while
converging to the truth at a minimax optimal rate.

The paper is organized as follows. In Section 2, we describe our specific
statistical framework and set notation. In Section 3, we introduce our
estimation procedure based on $\ell$-estimation and present our main result
regarding the risk bounds for the resulting estimators. We also provide an
explanation of why the deviation inequality we establish ensures the desired
robustness property of the estimators and compare them with the
$\rho$-estimators in that section. In Section 4, we delve into the
implementation of our $\ell$-type estimation approach on ReLU neural networks.
We establish uniform risk bounds over Hölder classes when the data are truly
i.i.d. and the regression function exists. By combining the lower bounds we
have derived, we demonstrate the minimax optimality of our estimators under
the well-specified scenario. The problem of circumventing the curse of
dimensionality is addressed in Section 5, where we impose structural
assumptions on the regression function $f^{\star}$. Section 6 is devoted to
most of the proofs in this paper.

##  2\. The statistical setting

Let $X_{i}=(W_{i},Y_{i})$, for $i\in\\{1,\ldots,n\\}$ be $n$ pairs of
independent, but not necessarily i.i.d., random variables with values in a
measurable product space
$({\mathscr{X}},{\mathcal{X}})=({\mathscr{W}}\times{\mathscr{Y}},{\mathcal{W}}\otimes{\mathcal{Y}})$.
Denote the set of all probabilities on $({\mathscr{Y}},{\mathcal{Y}})$ as
${\mathscr{T}}$. We assume that the conditional distribution of $Y_{i}$ given
$W_{i}=w_{i}$ exists and is given by the value at $w_{i}$ of a measurable
function $Q_{i}^{\star}$ from $({\mathscr{W}},{\mathcal{W}})$ to
${\mathscr{T}}$. We endow ${\mathscr{T}}$ with the Borel $\sigma$-algebra
${\mathcal{T}}$ associated with the total variation distance. Recall that when
given two probabilities $P_{1}$ and $P_{2}$ on a measurable space
$(A,{\mathscr{A}})$, the total variation distance $\|P_{1}-P_{2}\|_{TV}$
between $P_{1}$ and $P_{2}$ is defined as

$\|P_{1}-P_{2}\|_{TV}=\sup_{{\mathcal{A}}\in{\mathscr{A}}}\left[{P_{1}({\mathcal{A}})-P_{2}({\mathcal{A}})}\right]=\frac{1}{2}\int_{A}\left|\frac{dP_{1}}{d\mu}-\frac{dP_{2}}{d\mu}\right|d\mu,$

where $\mu$ is any reference measure that dominates both $P_{1}$ and $P_{2}$.
With this chosen ${\mathcal{T}}$, for any $i\in\\{1,\ldots,n\\}$, the mapping
$w\mapsto\|Q_{i}^{\star}(w)-R\|_{TV}$ on $({\mathscr{W}},{\mathcal{W}})$ is
measurable for any probability $R\in{\mathscr{T}}$.

Given a class of real-valued measurable functions $\overline{\mathcal{F}}$ on
${\mathscr{W}}$, we presume that, there exists a function
$f^{\star}\in\overline{\mathcal{F}}$ for which the conditional distributions
$Q_{i}^{\star}(W_{i})$ have the structure of
$Q_{f^{\star}(W_{i})}={\mathcal{N}}(f^{\star}(W_{i}),\sigma^{2})$ or are at
least in close proximity to it. The function $f^{\star}$ is what we refer to
as the regression function. It is worth emphasizing, as we mentioned in
Section 1, that our statistical model could potentially be misspecified: the
conditional distributions $Q_{i}^{\star}(W_{i})$ might not precisely take the
form $Q_{f^{\star}(W_{i})}$, or even if they did, the regression function
$f^{\star}$ might not belong to the class $\overline{\mathcal{F}}$. What we
are truly assuming is that the collection
$\\{Q_{f},\;f\in\overline{\mathcal{F}}\\}$ provides a suitable approximation
of the actual conditional distributions $Q_{i}^{\star}$, for
$i\in\\{1,\ldots,n\\}$.

Let ${\mathscr{Q}}_{{\mathscr{W}}}$ represent the collection of all
conditional probabilities from $({\mathscr{W}},{\mathcal{W}})$ to
$({\mathscr{T}},{\mathcal{T}})$, and define
${\mathscrbf{Q}}_{{\mathscr{W}}}={\mathscr{Q}}_{{\mathscr{W}}}^{n}$. As a
direct result, we obtain the $n$-tuple
${\mathbf{Q}}^{\star}=(Q^{\star}_{1},\ldots,Q^{\star}_{n})\in{\mathscrbf{Q}}_{{\mathscr{W}}}$.
We equip the space ${\mathscrbf{Q}}_{{\mathscr{W}}}$ with a distance metric
resembling the total variation distance. More precisely, for
${\mathbf{Q}}=(Q_{1},\ldots,Q_{n})$ and
${\mathbf{Q}}^{\prime}=(Q^{\prime}_{1},\ldots,Q^{\prime}_{n})$ in
${\mathscrbf{Q}}_{{\mathscr{W}}}$,

$\displaystyle\ell({\mathbf{Q}},{\mathbf{Q}}^{\prime})$
$\displaystyle=\frac{1}{n}{\mathbb{E}}\left[{\sum_{i=1}^{n}\|Q_{i}(W_{i})-Q^{\prime}_{i}(W_{i})\|_{TV}}\right]$
(1)
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\int_{{\mathscr{W}}}\|Q_{i}(w)-Q^{\prime}_{i}(w)\|_{TV}dP_{W_{i}}(w).$

Particularly, when $\ell({\mathbf{Q}},{\mathbf{Q}}^{\prime})=0$, it signifies
that $Q_{i}=Q^{\prime}_{i}$ $P_{W_{i}}$-a.s., for all $i$.

Building on the $n$ observations ${\bm{X}}=(X_{1},\ldots,X_{n})$, we will
introduce an estimation approach in the later section to develop an estimator
$\widehat{f}({\bm{X}})\in\overline{\mathcal{F}}$ for the potential regression
function $f^{\star}$ (which may not exist). Furthermore, we aim to estimate
the $n$-tuple ${\mathbf{Q}}^{\star}=(Q^{\star}_{1},\ldots,Q^{\star}_{n})$ by
means of the structure
${\mathbf{Q}}_{\widehat{f}}=(Q_{\widehat{f}},\ldots,Q_{\widehat{f}})$. We
assess the performance of the estimator ${\mathbf{Q}}_{\widehat{f}}$ for
${\mathbf{Q}}^{\star}$ through the measure
$\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\widehat{f}})$.

We denote $P=Q\cdot P_{W}$ when $P$ represents the distribution of a random
variable $(W,Y)\in{\mathscr{W}}\times{\mathscr{Y}}$, where the marginal
distribution of $W$ is $P_{W}$ and the conditional distribution of $Y$ given
$W$ is $Q$. One can observe that when $P_{1}=Q_{1}\cdot P_{W}$ and
$P_{2}=Q_{2}\cdot P_{W}$, the total variation distance between $P_{1}$ and
$P_{2}$ can be represented as

$\|P_{1}-P_{2}\|_{TV}=\int_{{\mathscr{W}}}\|Q_{1}(w)-Q_{2}(w)\|_{TV}dP_{W}(w).$

By defining $P_{i}^{\star}=Q_{i}^{\star}\cdot P_{W_{i}}$ and
$P_{i,f}=Q_{f}\cdot P_{W_{i}}$ for a measurable function $f$ that maps
${\mathscr{W}}$ to ${\mathbb{R}}$, we can represent
$\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{f})$ as the average total variation
distance over $n$ samples:

(2)
$\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{f})=\frac{1}{n}\sum_{i=1}^{n}\|P_{i}^{\star}-P_{i,f}\|_{TV}.$

In the case where $W_{i}$ are i.i.d. with the common distribution $P_{W}$ and
$Q^{\star}_{i}=Q^{\star}$ for all $i\in\\{1,\ldots,n\\}$, we may slightly
abuse the notation $\ell(Q^{\star},Q_{\widehat{f}})$ to measure the distance
between $Q^{\star}$ and $Q_{\widehat{f}}$ defined as

(3)
$\ell(Q^{\star},Q_{\widehat{f}})=\int_{{\mathscr{W}}}\|Q^{\star}(w)-Q_{\widehat{f}(w)}\|_{TV}dP_{W}(w).$

We conclude this section by introducing some notations that will be useful
later. We denote ${\mathbb{N}}^{*}$ the set of all positive natural numbers
and ${\mathbb{R}}_{+}^{*}$ the set of all positive real numbers. For any
$x\in{\mathbb{R}}$, we use the notation $\lfloor x\rfloor$ to represent the
largest integer strictly smaller than $x$, and the notation $\lceil x\rceil$
to represent the least integer greater than or equal to $x$. Given any set
$J$, we denote its cardinality by $|J|$. For a
${\mathbf{R}}\in{\mathscrbf{Q}}_{{\mathscr{W}}}$ and a set
${\mathbf{A}}\subset{\mathscrbf{Q}}_{{\mathscr{W}}}$, we define
$\ell({\mathbf{R}},{\mathbf{A}})=\inf_{{\mathbf{R}}^{\prime}\in{\mathbf{A}}}\ell({\mathbf{R}},{\mathbf{R}}^{\prime})$.
Unless otherwise specified, $\log$ denotes the logarithm function with base
$e$. Let $(E,{\mathcal{E}})$ be a measurable space and $\mu$ be a
$\sigma$-finite measure on $(E,{\mathcal{E}})$. For
$k\in\left[{1,+\infty}\right]$, we define ${\mathcal{L}}_{k}(E,\mu)$ the
collection of all the measurable functions $f$ on $(E,{\mathcal{E}},\mu)$ such
that $\|f\|_{k,\mu}<+\infty$, where

$\|f\|_{k,\mu}=\left\\{\begin{aligned}
&\left(\int_{E}|f|^{k}d\mu\right)^{1/k},&\mbox{for\ }k\in[1,+\infty),\\\
&\inf\\{K>0,\;|f|\leq K\;\mu-\mbox{a.e.}\\},&\mbox{for\
}k=\infty.\end{aligned}\right.$

We denote the associated equivalent classes as ${\mathbb{L}}_{k}(E,\mu)$ where
any two functions coincide for $\mu$-a.e. can not be distinguished. In
particular, we write the norm $\|\cdot\|_{k}$ with
$k\in\left[{1,+\infty}\right]$ when $\mu=\lambda$ is the Lebesgue measure.
Throughout the paper, $c$ or $C$ denotes positive numerical constant which may
vary from line to line.

##  3\. $\ell$-Type estimation under regression setting

We employ an $\ell$-type estimator, drawing inspiration from the concepts
outlined in a series of papers presented in Baraud, (2021) within a general
framework, as well as from the content of Baraud et al., (2022), which is
specifically dedicated to density estimation. Consider a set of $n$
independent random variables denoted as $X_{1},\ldots,X_{n}$, where their
values are drawn from a measured space $({\mathscr{X}},{\mathcal{X}})$. In
essence, $\ell$-estimation offers a versatile approach to acquiring a robust
estimator for the actual joint distribution ${\mathbf{P}}^{\star}$ of
$X_{1},\ldots,X_{n}$. The established $\ell$-estimation approach begins by
introducing a set of potential probabilities $\overline{\mathscrbf{P}}$,
intended to offer a suitable approximation of ${\mathbf{P}}^{\star}$. The
primary challenge in implementing $\ell$-estimation within a regression
framework lies in the absence of information concerning the marginal
distributions $P_{W_{i}}$ required for constructing candidate probabilities
and designing the estimation procedure. Moreover, our objective does not
encompass the task of estimating these marginal distributions. In this
scenario, further effort is necessary to implement $\ell$-type estimation and
establish a risk bound for the resulting estimator.

###  3.1. Constructing the $\ell$-type estimator

Let $\overline{\mathcal{F}}$ be a collection of real-valued measurable
functions on ${\mathscr{W}}$, which we call it a model. For any
$f\in\overline{\mathcal{F}}$, we denote $Q_{f}$ the conditional Gaussian
distribution induced by the function $f$, i.e., given any $w\in{\mathscr{W}}$,
$Q_{f(w)}$ is a normal distribution centered around $f(w)$, with a variance of
$\sigma^{2}$, and denote $q_{f(w)}$ the density function of the Gaussian
distribution $Q_{f(w)}$ with respect to the Lebesgue measure. To prevent any
measurability issue, we introduce the notation ${\mathcal{F}}$, representing
either a finite or, at most, a countable subset of $\overline{\mathcal{F}}$.
Subsequently, the majority of our discussion will be focused on the set
${\mathcal{F}}$. Nevertheless, as we delve into further details, it turns out
that through careful choice of ${\mathcal{F}}$, no approximation power will be
sacrificed in comparison to estimations based on $\overline{{\mathcal{F}}}$.

Given $f_{1},f_{2}\in{\mathcal{F}}$, we define for any
$(w,y)\in{\mathscr{W}}\times{\mathscr{Y}}$,

$t_{(f_{1},f_{2})}(w,y)=1\hskip-2.6pt{\rm
l}_{q_{f_{2}(w)}(y)>q_{f_{1}(w)}(y)}-Q_{f_{1}(w)}\left(q_{f_{2}(w)}>q_{f_{1}(w)}\right).$

Employing the function $t_{(f_{1},f_{2})}(\cdot,\cdot)$ produces the following
inequalities.

######  Lemma 1.

Let $P^{\star}=Q^{\star}\cdot P_{W}$ represent the distribution of a pair of
random variables $(W,Y)\in{\mathscr{W}}\times{\mathscr{Y}}$, where the first
marginal distribution is $P_{W}$, and the conditional distribution of $Y$
given $W$ is denoted by $Q^{\star}$. For any $f_{1},f_{2}\in{\mathcal{F}}$,
any $P_{W}$ and any $Q^{\star}\in{\mathscr{Q}}_{{\mathscr{W}}}$, we have

(4)
$\ell(Q_{f_{1}},Q_{f_{2}})-\ell(Q^{\star},Q_{f_{2}})\leq{\mathbb{E}}_{P^{\star}}\left[{t_{(f_{1},f_{2})}(W,Y)}\right]\leq\ell(Q^{\star},Q_{f_{1}}).$

The proof of Lemma 1 is deferred to Section 6.1. Lemma 1 implies that the
family of test statistics $t_{(f_{1},f_{2})}$ holds information concerning the
$\ell$-type distance between two of $Q_{f_{1}}$, $Q_{f_{2}}$, and $Q^{\star}$,
which is an essential property for constructing our final estimator.

For any $f_{1},f_{2}\in{\mathcal{F}}$ and $n$ pairs of observations
${\bm{X}}=(X_{1},\ldots,X_{n})$ with $X_{i}=(W_{i},Y_{i})$,
$i\in\\{1,\ldots,n\\}$, we design the function

${\mathbf{T}}_{l}({\bm{X}},f_{1},f_{2})=\sum_{i=1}^{n}t_{(f_{1},f_{2})}(W_{i},Y_{i})$

and set

${\mathbf{T}}_{l}({\bm{X}},f_{1})=\sup_{f_{2}\in{\mathcal{F}}}{\mathbf{T}}_{l}({\bm{X}},f_{1},f_{2}).$

Our final estimator of
${\mathbf{Q}}^{\star}=(Q^{\star}_{1},\ldots,Q^{\star}_{n})$ is defined as
${\mathbf{Q}}_{\widehat{f}}=(Q_{\widehat{f}},\ldots,Q_{\widehat{f}})$, where
$\widehat{f}({\bm{X}})$ is an $\epsilon$-minimizer over ${\mathcal{F}}$ of the
map $f_{1}\mapsto{\mathbf{T}}_{l}({\bm{X}},f_{1})$. More precisely, given
$\epsilon>0$, the $\ell$-type estimator within the set ${\mathcal{F}}$ is
defined as any measurable function $\widehat{f}({\bm{X}})$ of the random (and
non-void) set

${\mathscr{E}}({\bm{X}},\epsilon)=\left\\{f\in{\mathcal{F}},\;{\mathbf{T}}_{l}({\bm{X}},f)\leq\inf_{f^{\prime}\in{\mathcal{F}}}{\mathbf{T}}_{l}({\bm{X}},f^{\prime})+\epsilon\right\\}.$

######  Remark 1.

The parameter $\epsilon$ is devised to ensure the existence of the estimator
$\widehat{f}$. As we will explore in Section 3.2, it is prudent to choose a
relatively small value for $\epsilon$, specifically not significantly greater
than 1, as this choice improves the risk bound of an $\ell$-type estimator.
Specifically, when a function $f\in{\mathcal{F}}$ exists such that
${\mathbf{T}}_{l}({\bm{X}},f)=\inf_{f^{\prime}\in{\mathcal{F}}}{\mathbf{T}}_{l}({\bm{X}},f^{\prime})$,
it is advisable to prioritize this $f$ as the estimator $\widehat{f}$.

Furthermore, considering that
${\mathbf{T}}_{l}({\bm{X}},f)\geq{\mathbf{T}}_{l}({\bm{X}},f,f)=0$ for all
$f\in{\mathcal{F}}$, any function $\widehat{f}\in{\mathcal{F}}$ meeting the
condition $0\leq{\mathbf{T}}_{l}({\bm{X}},\widehat{f})\leq\epsilon$ qualifies
as an $\ell$-type estimator.

###  3.2. The performance of the $\ell$-type estimator

Before delving into the theoretical performance of our $\ell$-type estimator,
we lay the foundation by stating our main assumption on the model
$\overline{\mathcal{F}}$. To facilitate this, we introduce the following
definition:

######  Definition 1 (VC-subgraph).

An (open) subgraph of a function $f$ in $\overline{\mathcal{F}}$ is the subset
of ${\mathscr{W}}\times{\mathbb{R}}$ given by

${\mathscr{C}}_{f}=\left\\{(w,u)\in{\mathscr{W}}\times{\mathbb{R}},\;f(w)>u\right\\}.$

A collection $\overline{\mathcal{F}}$ of real-valued measurable functions on
${\mathscr{W}}$ is VC-subgraph with dimension not larger than $V$ if, for any
finite subset ${\mathcal{S}}\subset{\mathscr{W}}\times{\mathbb{R}}$ with
$|{\mathcal{S}}|=V+1$, there exists at least one subset $S$ of ${\mathcal{S}}$
such that for any $f\in\overline{\mathcal{F}}$, $S$ is not the intersection of
${\mathcal{S}}$ with ${\mathscr{C}}_{f}$, i.e.

$S\neq{\mathcal{S}}\cap{\mathscr{C}}_{f}\quad\text{whatever
$f\in\overline{\mathcal{F}}$.}$

Herein, we proceed to introduce our primary assumption concerning the model
$\overline{\mathcal{F}}$.

######  Assumption 1.

The class of functions $\overline{\mathcal{F}}$ is VC-subgraph on
${\mathscr{W}}$ with dimension not larger than $V\geq 1$.

Encompassing a range of widely employed examples, Assumption 1 is formulated
under a considerably broad scope. For instance, when $\overline{\mathcal{F}}$
is contained in a linear space with finite dimension $D$, Assumption 1 is
fulfilled with $V=D+1$ according to Lemma 2.6.15 of van der Vaart and Wellner,
(1996). Moreover, when $\overline{{\mathcal{F}}}$ represents a fully connected
ReLU neural network, it has been demonstrated in Bartlett et al., (2019)
[Theorem 7] that the VC-dimension of $\overline{{\mathcal{F}}}$ is linked to
the depth and width of the network. Further elaboration on $\ell$-estimation
based on neural networks will be provided in Section 4 and Section 5.

Building upon Assumption 1, we can establish the following non-asymptotic
exponential inequalities for the upper deviations of a total variation type
distance between the true distribution of the data and the estimated one based
on $\widehat{f}({\bm{X}})$.

######  Theorem 1.

Under Assumption 1, whatever the conditional distributions
${\mathbf{Q}}^{\star}=(Q^{\star}_{1},\ldots,Q^{\star}_{n})$ of the $Y_{i}$
given $W_{i}$ and the distributions of $W_{i}$, any $\ell$-type estimator
$\widehat{f}$ based on the class ${\mathcal{F}}$ satisfies that for any
$\overline{f}\in{\mathcal{F}}$ and any $\xi>0$, with a probability at least
$1-e^{-\xi}$,

(5) $\ell({\mathbf{Q}}_{\overline{f}},{\mathbf{Q}}_{\widehat{f}})\leq
2\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+291.2\sqrt{\frac{V}{n}}+14573.4\frac{V}{n}+\sqrt{\frac{8(\xi+\log
2)}{n}}+\frac{\epsilon}{n}.$

In particular, with the triangle inequality,

(6) $\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\widehat{f}})\leq
3\ell({\mathbf{Q}}^{\star},{\mathscrbf{Q}})+291.2\sqrt{\frac{V}{n}}+14573.4\frac{V}{n}+\sqrt{\frac{8(\xi+\log
2)}{n}}+\frac{\epsilon}{n},$

where ${\mathscrbf{Q}}=\\{{\mathbf{Q}}_{f},\;f\in{\mathcal{F}}\\}$. As a
consequence of (6), for any $n\geq V$, integration with respect to $\xi>0$
yields the following risk bound for the resulting estimator
${\mathbf{Q}}_{\widehat{f}}=(Q_{\widehat{f}},\ldots,Q_{\widehat{f}})$

(7)
${\mathbb{E}}\left[{\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\widehat{f}})}\right]\leq
C_{\epsilon}\left[{\ell({\mathbf{Q}}^{\star},{\mathscrbf{Q}})+\sqrt{\frac{V}{n}}}\right],$

where $C_{\epsilon}>0$ is a numerical constant depending on $\epsilon$ only.

The proof of Theorem 1 is deferred to Section 6.2. Let us now provide some
remarks regarding this result.

######  Remark 2.

Consider the set
$\overline{\mathscrbf{Q}}=\\{{\mathbf{Q}}_{f},\;f\in\overline{\mathcal{F}}\\}$.
It is clear that if ${\mathscrbf{Q}}$ is dense in $\overline{\mathscrbf{Q}}$
with respect to the (pseudo) distance $\ell$, both (6) and (7) also remain
valid when replacing ${\mathscrbf{Q}}$ with $\overline{\mathscrbf{Q}}$. This
is the situation in which the subset ${\mathcal{F}}$ is dense in
$\overline{\mathcal{F}}$ with respect to the topology of pointwise
convergence. For further insights in this direction, we refer to Section 4.2
of Baraud and Birgé, (2018). For the sake of simplicity in our explanation,
let us temporarily assume in this section that ${\mathscrbf{Q}}$ is dense in
$\overline{\mathscrbf{Q}}$ with respect to $\ell$.

######  Remark 3.

According to (7), the risk of the resulting estimator is bounded, up to a
numerical constant, by the sum of two terms. The term
$\ell({\mathbf{Q}}^{\star},\overline{\mathscrbf{Q}})$ corresponds to the
approximation error incurred by employing the model $\overline{\mathcal{F}}$,
while $\sqrt{V/n}$ illustrates the complexity of the considered model
$\overline{\mathcal{F}}$. Hence, a suitable model $\overline{\mathcal{F}}$
should strike a balance between these two factors, namely, a model that is not
excessively complex yet offers a good approximation of the underlying
regression function.

######  Remark 4.

In the favourable situation where the data $X_{i}=(W_{i},Y_{i})$ are truly
i.i.d. with $Q^{\star}_{i}=Q_{f^{\star}}$, $i\in\\{1,\ldots,n\\}$ for some
$f^{\star}\in\overline{\mathcal{F}}$, we can deduce from (7) that

${\mathbb{E}}\left[{\ell(Q_{f^{\star}},Q_{\widehat{f}})}\right]\leq
C_{\epsilon}\sqrt{\frac{V}{n}}.$

In typical situations, the value of $V$ aligns with the magnitude of
parameters necessary to parametrize $\overline{\mathcal{F}}$, which cannot be
improved in general. As we shall observe in Section 4.2, the above risk bound
will lead to an optimal rate of convergence in the minimax sense when the
regression function $f^{\star}$ is assumed to be a smooth function of
regularity $\alpha$.

######  Remark 5.

The term $\ell({\mathbf{Q}}^{\star},\overline{\mathscrbf{Q}})$ elucidates the
robustness property of the resulting estimator concerning model
misspecification. To illustrate, let us consider the general scenario where
the data are only independent and the true joint distribution is given by

(8)
${\mathbf{P}}^{\star}=\bigotimes_{i=1}^{n}P^{\star}_{i}=\bigotimes_{i=1}^{n}\left[(1-\beta_{i})P_{i,\overline{f}}+\beta_{i}R_{i}\right],\quad\quad\sum_{i=1}^{n}\beta_{i}\leq\frac{n}{2},$

with some $\overline{f}\in\overline{\mathcal{F}}$,
$P_{i,\overline{f}}=Q_{\overline{f}}\cdot P_{W_{i}}$, $R_{i}$ being an
arbitrary distribution on ${\mathscr{X}}={\mathscr{W}}\times{\mathscr{Y}}$ and
$\beta_{i}$ taking values in $\left[{0,1}\right]$ for all
$i\in\\{1,\ldots,n\\}$. With the connection (2) between the pseudo distance
$\ell$ and $\|\cdot\|_{TV}$, we can deduce from (7) that

$\displaystyle{\mathbb{E}}\left[{\frac{1}{n}\sum_{i=1}^{n}\|P^{\star}_{i}-P_{i,\widehat{f}}\|_{TV}}\right]$
$\displaystyle\leq
C_{\epsilon}\left[{\frac{1}{n}\sum_{i=1}^{n}\|P^{\star}_{i}-P_{i,\overline{f}}\|_{TV}+\sqrt{\frac{V}{n}}}\right]$
(9) $\displaystyle\leq
C_{\epsilon}\left[{\frac{1}{n}\sum_{i=1}^{n}\beta_{i}+\sqrt{\frac{V}{n}}}\right],$

where the second inequality comes from the fact that $\|\cdot\|_{TV}$ is
bounded by 1. The above result implies that as long as the quantity
$(\sum_{i=1}^{n}\beta_{i})/n$ remains small compared to the term $\sqrt{V/n}$,
the performance of the resulting estimator will not deteriorate significantly
in comparison to the ideal situation presented in Remark 4.

The formulation (8) can be utilized to provide a more detailed explanation of
the stability of $\ell$-type estimation procedure. More precisely, in the case
of the presence of outliers, the observations include several outliers, the
indices of which are marked as a non-empty subset $J$ of $\\{1,\ldots,n\\}$.
For any $i\in J$, $R_{i}=\delta_{a_{i}}$ and $\beta_{i}=1\hskip-2.6pt{\rm
l}_{i\in J}$ for all $i\in\\{1,\ldots,n\\}$. The bound (9) indicates that our
estimation procedure remains stable as long as $|J|/n$ remains small compared
to $\sqrt{V/n}$. This accounts for the robustness when the outliers present.
Under another scenario, where the data are contaminated, $(W_{i},Y_{i})$ are
i.i.d., and $P_{W_{i}}=P_{W}$. A portion $\beta\in(0,1/2]$ of the $n$ samples
is drawn according to an arbitrary distribution $R_{i}=R$ (where $R$ is not
equal to $P_{i,\overline{f}}$), while the remaining part follows the
distribution $P_{i,\overline{f}}$. In this case, as an immediate consequence
of (9), the performance of our estimator remains stable as long as the
contamination proportion $\beta$ remains small compared to the value of
$\sqrt{V/n}$.

###  3.3. Connection to ${\mathbb{L}}_{1}$-distance between the regression
functions

As we have seen in Section 3.2, we establish non-asymptotic inequalities for
the upper deviations of a total variation type distance between the true
conditional distributions and the estimated one based on $\widehat{f}$. In the
context of a regression setting where the data are truly i.i.d. and follow the
common marginal distribution $P_{W}$, the function $f^{\star}$ exists, such
that $Q_{i}^{\star}=Q_{f^{\star}}$. It would be interesting to investigate the
performance of the $\ell$-type estimator $\widehat{f}({\bm{X}})$ in relation
to the regression function $f^{\star}$, utilizing a suitable distance metric,
as typically considered in the literature. Given two real-valued functions $f$
and $f^{\prime}$ on ${\mathscr{W}}$, it turns out that
$\ell(Q_{f},Q_{f^{\prime}})$ can be related to the
${\mathbb{L}}_{1}(P_{W})$-distance between $f$ and $f^{\prime}$. We present
the result as follows.

######  Lemma 2.

For any two measurable real-valued functions $f,f^{\prime}$ on
${\mathscr{W}}$, and any $w\in{\mathscr{W}}$, we have

(10)
$\|Q_{f(w)}-Q_{f^{\prime}(w)}\|_{TV}=1-2\Phi\left(-\frac{|f^{\prime}(w)-f(w)|}{2\sigma}\right),$

where the notation $\Phi$ stands for the cumulative distribution function of
the standard normal distribution. Consequently,

(11)
$0.78\min\left\\{\frac{\|f-f^{\prime}\|_{1,P_{W}}}{\sqrt{2\pi}\sigma},1\right\\}\leq\ell(Q_{f},Q_{f^{\prime}})\leq\min\left\\{\frac{\|f-f^{\prime}\|_{1,P_{W}}}{\sqrt{2\pi}\sigma},1\right\\}.$

###### Proof.

For any two probabilities $P$ and $R$ on the measured space
$({\mathscr{X}},{\mathcal{X}})$, it is well known that the total variation
distance can equivalently be written as $\|P-R\|_{TV}=R(r>p)-P(r>p),$ where
$p$ and $r$ stand for the respective densities of $P$ and $R$ with respect to
some common dominating measure $\mu$. Therefore, a fundamental calculation
reveals that for any $w\in{\mathscr{W}}$,

$\displaystyle\|Q_{f(w)}-Q_{f^{\prime}(w)}\|_{TV}$
$\displaystyle=Q_{f^{\prime}(w)}\left(q_{f^{\prime}(w)}>q_{f(w)}\right)-Q_{f(w)}\left(q_{f^{\prime}(w)}>q_{f(w)}\right)$
$\displaystyle=\left[{1-\Phi\left(-\frac{|f^{\prime}(w)-f(w)|}{2\sigma}\right)}\right]-\Phi\left(-\frac{|f^{\prime}(w)-f(w)|}{2\sigma}\right)$
(12)
$\displaystyle=1-2\Phi\left(-\frac{|f^{\prime}(w)-f(w)|}{2\sigma}\right),$

which concludes the equality (10). We also note from (12) that

$\|Q_{f(w)}-Q_{f^{\prime}(w)}\|_{TV}={\mathbb{P}}\left[{|Z|\leq\frac{1}{2}\left(\frac{|f^{\prime}(w)-f(w)|}{\sigma}\right)}\right],$

where $Z$ is a standard real-valued Gaussian random variable. Recall that

(13)
$\ell(Q_{f},Q_{f^{\prime}})=\int_{{\mathscr{W}}}\|Q_{f(w)}-Q_{f^{\prime}(w)}\|_{TV}dP_{W}(w).$

Based on (13), the conclusion of (11) follows by applying Lemma 1 in Baraud,
(2021) with $d=1$ and replacing $|m-m^{\prime}|$ with
$(|f^{\prime}(w)-f(w)|)/\sigma$. ∎

The above result indicates that when the two functions $f$ and $f^{\prime}$
are sufficiently close to each other with respect to the
${\mathbb{L}}_{1}(P_{W})$-distance, the quantity $\ell(Q_{f},Q_{f^{\prime}})$
is of order $\|f-f^{\prime}\|_{1,P_{W}}/(\sqrt{2\pi}\sigma)$. Conversely, when
$f$ and $f^{\prime}$ are far apart, the value of $\ell(Q_{f},Q_{f^{\prime}})$
remains approximately of the order of 1. Combining Lemma 2 with (7), we can
deduce that

(14)
$\displaystyle\min\left\\{\frac{{\mathbb{E}}\left[{\|f^{\star}-\widehat{f}\|_{1,P_{W}}}\right]}{\sqrt{2\pi}\sigma},1\right\\}\leq
C_{\epsilon}\left[{\inf_{f\in{\mathcal{F}}}\ell(Q_{f^{\star}},Q_{f})+\sqrt{\frac{V}{n}}}\right],$

where $C_{\epsilon}>0$ is a numerical constant depending on $\epsilon$ only.
As we shall see it later, in typical applications, if we can find a nice model
to approximate the regression function $f^{\star}$ in the sense that the right
hand of (14) is smaller than 1, then we finally obtain a risk bound for
$\widehat{f}({\bm{X}})$ with respect to the ${\mathbb{L}}_{1}$-distance:

${\mathbb{E}}\left[{\|f^{\star}-\widehat{f}\|_{1,P_{W}}}\right]\leq
C_{\epsilon,\sigma}\left[{\inf_{f\in{\mathcal{F}}}\|f^{\star}-f\|_{1,P_{W}}+\sqrt{\frac{V}{n}}}\right],$

where $C_{\epsilon,\sigma}$ is a numerical constant depending on
$\epsilon,\sigma$ only.

###  3.4. Comparison with $\rho$-estimation

As mentioned in Section 3.2, one notable feature of the $\ell$-type estimators
is their robustness under misspecification. Interestingly, the
$\rho$-estimators also exhibit robustness properties, but they are quantified
using a Hellinger-type distance, rather than the one based on the total
variation distance. For a more comprehensive understanding of the
$\rho$-estimation methodology, one can refer to Baraud and Birgé, (2018) and
Baraud and Chen, (2020), with the latter primarily focusing on the regression
setting. It is worth noting that while there exists some connection between
the Hellinger distance and the total variation distance, they are not
equivalent in general. The main distinctions between these two types of
estimators has been examined in Section 7.1 of Baraud, (2021) which includes
an illustration of regression under a fixed design. Leveraging the results we
have established in Section 3.2 and 3.3, we are therefore able to delve deeper
in this direction, especially under a random regression design setting.

To illustrate simply, we assume the data are truly i.i.d. with
$P_{W_{i}}=P_{W}$ and $Q^{\star}_{i}=Q^{\star}$, for all
$i\in\\{1,\ldots,n\\}$. We write $P^{\star}=Q^{\star}\cdot P_{W}$ the true
distribution of $(W,Y)\in{\mathscr{W}}\times{\mathscr{Y}}$. For some
$f\in{\mathcal{F}}$, provided the term $\ell(Q^{\star},Q_{f})$ and $1/n$ are
both sufficiently small, employing Lemma 2, one can deduce from (5) that the
$\ell$-type estimator $\widehat{f}_{\ell}({\bm{X}})$ satisfies

(15) ${\mathbb{E}}\left[{\|f-\widehat{f}_{\ell}\|_{1,P_{W}}}\right]\leq
C_{\sigma,\epsilon}\left[{\|P^{\star}-P_{f}\|_{TV}+\sqrt{\frac{V}{n}}}\right],$

where $P_{f}=Q_{f}\cdot P_{W}$. From another point of view, we can deduce,
through a slight modification of Theorem 1 in Baraud and Chen, (2020), that
for any $f\in{\mathcal{F}}$, the $\rho$-estimator
$\widehat{f}_{\rho}({\bm{X}})$ complies with the following

${\mathbb{E}}\left[{h^{2}(P_{f},P_{\widehat{f}_{\rho}})}\right]\leq
C\left[{h^{2}(P^{\star},P_{f})+\frac{V(1+\log n)}{n}}\right],$

where $C>0$ is some numerical constant and $h$ stands for the Hellinger
distance. Considering the fact that

$\displaystyle h^{2}(P_{f},P_{\widehat{f}_{\rho}})$
$\displaystyle=\int_{{\mathscr{W}}}1-\exp\left[{-\frac{|f(w)-\widehat{f}_{\rho}(w)|^{2}}{8\sigma^{2}}}\right]dP_{W}(w)$
$\displaystyle\geq(1-e^{-1})\left(\frac{\|f-\widehat{f}_{\rho}\|^{2}_{2,P_{W}}}{8\sigma^{2}}\wedge
1\right),$

we can deduce, using Hölder’s inequality and a similar argument to that used
in obtaining (15), that for some $f\in{\mathcal{F}}$, given the term
$h^{2}(P^{\star},P_{f})$ and $1/n$ are both sufficiently small

(16) ${\mathbb{E}}\left[{\|f-\widehat{f}_{\ell}\|_{1,P_{W}}}\right]\leq
C_{\sigma}\left[{h(P^{\star},P_{f})+\sqrt{\frac{V(1+\log n)}{n}}}\right].$

If we put the numerical constants $C_{\sigma,\epsilon}$, $C_{\sigma}$ aside,
the main difference between the two risk bounds lie in the fact that they
express the robustness of the two different estimators by the approximation
term $\|P^{\star}-P_{f}\|_{TV}$ and $h(P^{\star},P_{f})$ respectively. With
the connection that for any two probabilities $P_{1},P_{2}$,

$\|P_{1}-P_{2}\|_{TV}\leq\sqrt{2}h(P_{1},P_{2}),$

we can conclude that the stability of the $\ell$-type estimators will not be
significantly worse than the $\rho$-estimators. In fact, the $\ell$-type
estimators can posses much more robustness than the $\rho$-estimators. To
explain it in details, consider the misspecified formulation:

$P^{\star}=(1-\beta)P_{f^{\star}}+\beta R,\quad\mbox{for some small\
}\beta\in(0,1),$

where $f^{\star}\in{\mathcal{F}}$, $R\not=P_{f^{\star}}$ is any arbitrary
distribution on ${\mathscr{X}}={\mathscr{W}}\times{\mathscr{Y}}$. On the one
hand, we can calculate that

(17) $\|P^{\star}-P_{f^{\star}}\|_{TV}=\beta\|P_{f^{\star}}-R\|_{TV},$

which is of the order of magnitude $\beta$. On the other hand, we have

(18) $h(P^{\star},P_{f^{\star}})\leq\sqrt{1-\sqrt{1-\beta}},$

which is at most of the order of magnitude $\sqrt{\beta/2}$. Therefore, for
small values of $\beta$, the above computation indicates that the term
$h(P^{\star},P_{f^{\star}})$ is much larger than
$\|P^{\star}-P_{f^{\star}}\|_{TV}$. Combining (15) with (17), we deduce that
the $\ell$-type estimators remain stable as long as $\beta$ is small as
compared to $1/\sqrt{n}$. Combining (16) with (18), we know that the
performance of the $\rho$-estimators deteriorate immediately as long as
$\beta$ becomes large as compared to $(\log n)/n$. This analysis implies that
the $\ell$-type estimators possess more robustness compared to the ones
obtained from $\rho$-estimation.

##  4\. Applications of $\ell$-type Estimation Using Neural Networks

In recent years, experimental findings have demonstrated the significant
success of neural networks modeling in various applications. From a
theoretical perspective, it has been observed that neural networks, especially
deep ones (see, for example, Schmidt-Hieber, (2020) and Suzuki and Nitanda,
(2021)), possess a natural advantage over classical methods when approximating
functions with specific characteristics. In this section, we will discuss
$\ell$-type estimation for models based on neural networks. The covariates
$W_{i}$ are assumed to be i.i.d. on ${\mathscr{W}}=\left[{0,1}\right]^{d}$,
following the common distribution $P_{W}$, while $Q_{i}^{\star}=Q^{\star}$
holds for all $i\in\\{1,\ldots,n\\}$.

###  4.1. ReLU feedforward neural networks

We start with introducing some preliminaries of the ReLU feedforward neural
networks. Recall the Rectifier Linear Unit (ReLU) activation function
$\sigma:{\mathbb{R}}\rightarrow{\mathbb{R}}$, which is defined as

$\sigma(x)=\max\\{0,x\\}.$

For any vector ${\bm{x}}=(x_{1},\ldots,x_{p})^{\top}\in{\mathbb{R}}^{p}$,
where $p\in{\mathbb{N}}^{*}$, the notation $\sigma({\bm{x}})$ represents the
activation function applied component-wise, defined as follows:

$\sigma({\bm{x}})=(\max\\{0,x_{1}\\},\ldots,\max\\{0,x_{p}\\})^{\top}.$

A fundamental and extensively employed type of feedforward neural networks in
practice is the multi-layer perceptrons, where the neurons in consecutive
layers are fully connected through linear transformation matrices. In our
later discussion on applying the $\ell$-type estimation, we will focus on the
multi-layer perceptrons with ReLU activation function. To begin, let’s
introduce the expression of the multi-layer perceptrons under consideration.
For any vector ${\bm{p}}=(p_{0},\ldots,p_{L+1})\in({\mathbb{N}}^{*})^{L+2}$
with $p_{0}=d$ and $p_{L+1}=1$ and $L\in{\mathbb{N}}^{*}$, we denote the
multi-layer perceptron $\overline{\mathcal{F}}_{(L,{\bm{p}})}$ as a collection
of functions of the form:

$f:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}},\quad{\bm{w}}\mapsto
f({\bm{w}})=M_{L}\circ\sigma\circ M_{L-1}\circ\cdots\circ\sigma\circ
M_{0}({\bm{w}}),$

where

$M_{l}({\bm{y}})=A_{l}({\bm{y}})+b_{l},\mbox{\quad for\ }l=0,\ldots,L,$

$A_{l}$ is a $p_{l+1}\times p_{l}$ weight matrix and the shift vector $b_{l}$
is of size $p_{l+1}$ for any $l\in\\{0,\ldots,L\\}$. In the first layer, the
input data consists of the values of the predictor $W$, whereas the last layer
represents the output. With the expression given above, we say that the
network $\overline{\mathcal{F}}_{(L,{\bm{p}})}$ comprises $L$ hidden layers
and a total of $(L+2)$ layers. For $l\in\\{1,\ldots,L\\}$, we refer to $p_{l}$
as the width of the $l$-th hidden layer. The entries in these weight matrices
and vectors typically vary in ${\mathbb{R}}$ or a subinterval of
${\mathbb{R}}$, which is what we refer to as parameters. In the latter
scenario, we employ the notation
$\overline{\mathcal{F}}_{(L,{\bm{p}},K)}\subset\overline{\mathcal{F}}_{(L,{\bm{p}})}$,
denoting the set of all functions with parameters ranging within the interval
$\left[{-K,K}\right]$. Furthermore, we use the notation
${\mathcal{F}}_{(L,{\bm{p}})}$ (or ${\mathcal{F}}_{(L,{\bm{p}},K)}$) for the
multi-layer perceptron, which shares the same architecture as
$\overline{\mathcal{F}}_{(L,{\bm{p}})}$ (or
$\overline{\mathcal{F}}_{(L,{\bm{p}},K)}$ respectively), but with the
distinction that all the parameters take values in ${\mathbb{Q}}$. In some of
our application scenarios, it suffices to consider a multi-layer perceptron
with a rectangular design, where $p_{l}=p$ for all $l\in\\{1,\ldots,L\\}$. In
this case, we may use the simplified notation ${\mathcal{F}}_{(L,p)}$ (or
${\mathcal{F}}_{(L,p,K)}$) to represent the class
${\mathcal{F}}_{(L,{\bm{p}})}$ (or ${\mathcal{F}}_{(L,{\bm{p}},K)}$
respectively) for ${\bm{p}}=(d,p,\ldots,p,1)$.

We discuss the implementation of the $\ell$-type estimation on ReLU neural
networks ${\mathcal{F}}_{(L,{\bm{p}},K)}$. To implement the procedure
introduced in Section 3, we work on the countable subset
${\mathcal{F}}_{(L,{\bm{p}},K)}$ of the model
$\overline{\mathcal{F}}_{(L,{\bm{p}},K)}$. We can establish the following
result.

######  Lemma 3.

For any $L\in{\mathbb{N}}^{*}$,
${\bm{p}}=(p_{0},\ldots,p_{L+1})\in({\mathbb{N}}^{*})^{L+2}$ with $p_{0}=d$,
$p_{L+1}=1$ and a finite positive constant $K$, the class of functions
${\mathcal{F}}_{(L,{\bm{p}},K)}$ is dense in
$\overline{\mathcal{F}}_{(L,{\bm{p}},K)}$ with respect to the supremum norm
$\|\cdot\|_{\infty}$.

The proof of Lemma 3 is postponed to Section 6.3. Lemma 3 ensures that our
estimation approach applied to the countable model
${\mathcal{F}}_{(L,{\bm{p}},K)}$ does not compromise approximation power
compared to $\overline{\mathcal{F}}_{(L,{\bm{p}},K)}$.

The following proposition establishes VC-dimensional bounds for rectangular
multi-layer perceptrons employing a ReLU activation function. This result can
be derived from Proposition 5 in Chen, (2022), which also aligns with those
stated in Theorem 7 of Bartlett et al., (2019).

######  Proposition 1.

For any $L\in{\mathbb{N}}^{*}$, $p\in{\mathbb{N}}^{*}$, the class of functions
$\overline{\mathcal{F}}_{(L,p)}$ is a VC-subgraph on ${\mathscr{W}}$ with
dimension

(19)
$V(\overline{\mathcal{F}}_{(L,p)})\leq(L+1)\left(s+1\right)\log_{2}\left[{2\left(2e(L+1)\left(\frac{pL}{2}+1\right)\right)^{2}}\right],$

where $s=p^{2}(L-1)+p(L+d+1)+1$.

This result shows the connection between the VC-dimensional bounds and the
depth and width of ReLU rectangular multi-layer perceptrons. Specifically, for
any finite constant $K>0$, as
$\overline{\mathcal{F}}_{(L,p,K)}\subset\overline{\mathcal{F}}_{(L,p)}$, the
dimensional bounds (19) also apply to the class
$\overline{\mathcal{F}}_{(L,p,K)}$. We will use Proposition 1 along with other
results to derive the risk bounds for the $\ell$-type estimators when applying
our approach to ReLU feedforward neural networks.

###  4.2. Approximating functions in Hölder space

In this section, we examine the performance of the $\ell$-type estimators
implemented on the ReLU feedforward neural networks. We consider the
regression setting, where the regression function $f^{\star}$ exists, and we
assume that it belongs to an $\alpha$-smoothness Hölder class.

Given $t\in{\mathbb{N}}^{*}$ and $\alpha\in{\mathbb{R}}_{+}^{*}$, we define
${\mathcal{H}}^{\alpha}(D,B)$ an $\alpha$-Hölder ball with radius $B$ as the
collection of functions $f:D\subset{\mathbb{R}}^{t}\rightarrow{\mathbb{R}}$
such that

$\max_{\begin{subarray}{c}{\bm{\beta}}=(\beta_{1},\ldots,\beta_{t})^{\top}\in{\mathbb{N}}^{t}\\\
\sum_{j=1}^{t}\beta_{j}\leq\lfloor\alpha\rfloor\end{subarray}}\|\partial^{\bm{\beta}}f\|_{\infty}\leq
B\quad\mbox{and}\ \max_{\begin{subarray}{c}{\bm{\beta}}\in{\mathbb{N}}^{t}\\\
\sum_{j=1}^{t}\beta_{j}=\lfloor\alpha\rfloor\end{subarray}}\sup_{\begin{subarray}{c}{\bm{x}},{\bm{y}}\in
D\\\
{\bm{x}}\not={\bm{y}}\end{subarray}}\frac{\left|\partial^{\bm{\beta}}f({\bm{x}})-\partial^{\bm{\beta}}f({\bm{y}})\right|}{\|{\bm{x}}-{\bm{y}}\|_{2}^{\alpha-\lfloor\alpha\rfloor}}\leq
B,$

where for any
${\bm{\beta}}=(\beta_{1},\ldots,\beta_{t})^{\top}\in{\mathbb{N}}^{t}$,
$\partial^{\bm{\beta}}=\partial^{\beta_{1}}\cdots\partial^{\beta_{t}}$.

Based on the notation introduced above, in this section, we assume that
$Q^{\star}=Q_{f^{\star}}$, where
$f^{\star}\in{\mathcal{H}}^{\alpha}(\left[{0,1}\right]^{d},B)$, with a
specified smoothness index $\alpha\in{\mathbb{R}}_{+}^{*}$ and a finite
constant $B>0$. For any $\alpha\in{\mathbb{R}}_{+}^{*}$, the following result
demonstrates the error introduced by various ReLU neural networks when
approximating the class ${\mathcal{H}}^{\alpha}(\left[{0,1}\right]^{d},B)$, as
deduced from Corollary 3.1 of Jiao et al., (2023).

######  Proposition 2.

Assume that $f\in{\mathcal{H}}^{\alpha}(\left[{0,1}\right]^{d},B)$ with
$\alpha\in{\mathbb{R}}_{+}^{*}$ and a finite constant $B>0$. For any
$M,N\in{\mathbb{N}}^{*}$, there exists a function $\overline{f}$ implemented
by a ReLU neural network $\overline{\mathcal{F}}_{(L,p)}$ with a width of

$p=38(\lfloor\alpha\rfloor+1)^{2}3^{d}d^{\lfloor\alpha\rfloor+1}N\lceil\log_{2}(8N)\rceil$

and a depth of

$L=21(\lfloor\alpha\rfloor+1)^{2}M\lceil\log_{2}(8M)\rceil+2d$

such that

$\big{|}f({\bm{w}})-\overline{f}({\bm{w}})\big{|}\leq
19B(\lfloor\alpha\rfloor+1)^{2}d^{\lfloor\alpha\rfloor+\frac{\alpha\vee
1}{2}}(NM)^{-\frac{2\alpha}{d}},$

for all ${\bm{w}}\in\left[{0,1}\right]^{d}$.

In fact, several approximation results have been established regarding the
Hölder class of smoothness functions, for instance in Chen et al., (2019),
Schmidt-Hieber, (2020), and Nakada and Imaizumi, (2020), among others. The
reason why we consider using Proposition 2 is mainly due to two aspects.
Firstly, unlike most existing results where the prefactor in the error bound
depends exponentially on the dimension $d$, the prefactor in this error bound
depends only polynomially on the dimension $d$. Secondly, it offers specific
structures of the neural networks to be considered, thus making the result
more informative.

Building upon the results of Theorem 1, Proposition 1, 2, and Lemma 3, we
derive the risk bounds for the $\ell$-type estimators implemented by different
networks as follows.

######  Corollary 1.

For any $N,M\in{\mathbb{N}}^{*}$, no matter what the distribution of $W$ is,
the $\ell$-type estimator $\widehat{f}({\bm{X}})$ taking values in the network
class ${\mathcal{F}}_{(L,p,K)}$ with

$p=38(\lfloor\alpha\rfloor+1)^{2}3^{d}d^{\lfloor\alpha\rfloor+1}N\lceil\log_{2}(8N)\rceil,$
$L=21(\lfloor\alpha\rfloor+1)^{2}M\lceil\log_{2}(8M)\rceil+2d$

and a sufficiently large $K$, satisfies that for any
$f^{\star}\in{\mathcal{H}}^{\alpha}(\left[{0,1}\right]^{d},B)$ and $n\geq
V(\overline{\mathcal{F}}_{(L,p)})$,

(20) ${\mathbb{E}}\left[{\ell(Q_{f^{\star}},Q_{\widehat{f}})}\right]\leq
C_{\epsilon,\sigma,\alpha,d,B}\left[{(NM)^{-2\alpha/d}+\frac{NM}{\sqrt{n}}\left(\log_{2}(2N)\log_{2}(2M)\right)^{3/2}}\right],$

where $C_{\epsilon,\sigma,\alpha,d,B}$ is a constant depending on
$\epsilon,\sigma,\alpha,d$ and $B$ only.

In particular, if we take $N=1$ and $M=\lceil n^{d/2(d+2\alpha)}\rceil$,
combining Lemma 2 with (20) allows us to deduce that:

(21) ${\mathbb{E}}\left[{\ell(Q_{f^{\star}},Q_{\widehat{f}})}\right]\leq
C_{\epsilon,\sigma,\alpha,d,B}n^{-\frac{\alpha}{d+2\alpha}}\left(\log
n\right)^{3/2}.$

For $n$ being sufficiently large such that the right-hand side of (21) is
smaller that 0.78, according to Lemma 2, (21) is equivalent to

${\mathbb{E}}\left[{\|{f^{\star}}-\widehat{f}\|_{1,P_{W}}}\right]\leq
C_{\epsilon,\sigma,\alpha,d,B}n^{-\frac{\alpha}{d+2\alpha}}\left(\log
n\right)^{3/2},$

which is the typical rate of convergence with respect to the
${\mathbb{L}}_{1}(P_{W})$-norm.

The proof of Corollary 1 is deferred to Section 6.4. Our remarks are provided
below.

######  Remark 6.

As we will see later it in Theorem 2, the convergence rate
$n^{-\alpha/(d+2\alpha)}$ is minimax optimal with respect to the distance
$\ell(\cdot,\cdot)$, at least when $W$ is uniformly distributed on
$\left[{0,1}\right]^{d}$. Therefore, the risk bound (21) we obtained is
optimal up to a logarithmic factor. As it was shown in Section 7 of Baraud,
(2021), $\ell$-estimators are not always optimal when addressing various
estimation problems, which differs from $\rho$-estimators. However, by
combining the upper bound (21) and the subsequent lower bound stated in
Theorem 2, we demonstrate that implementing the $\ell$-type estimation
procedure is optimal within our framework and offers more robustness compared
to $\rho$-estimators.

######  Remark 7.

A noteworthy aspect of the presented result is that the stochastic error is
not dependent on the upper bound of the sup-norms for all functions within the
class $\overline{\mathcal{F}}_{(L,p,K)}$. This is not the case, for example,
in the results established in Lemma 4 of Schmidt-Hieber, (2020) and Theorem
4.2 of Jiao et al., (2023), both of which analyze the performance of the least
squares estimator. As a consequence, the final risk bound they established
deteriorates with the enlargement of the model they considered due to the
inclusion of such an upper bound in their stochastic error terms. From this
perspective, our estimation method does not suffer from this drawback.
Therefore, we can accommodate a sufficiently large value of $K$ without
compromising the risk bound for the resulting estimator.

##  5\. Circumventing the curse of dimensionality

As we observed in Section 4, the minimax optimal rate over an $\alpha$-Hölder
class on ${\mathscr{W}}=\left[{0,1}\right]^{d}$ is of order
$n^{-\alpha/(d+2\alpha)}$. This rate slows down significantly as the
dimensionality $d$ increases, a phenomenon known as the curse of
dimensionality. To overcome this issue, in this section, we introduce
structural assumptions on $f^{\star}$ and construct specific models using deep
ReLU neural networks to implement our procedure.

One natural structure for the regression function $f^{\star}$ for neural
networks to exhibit advantages is a composition of multiple functions, which
was previously explored by Schmidt-Hieber, (2020). More precisely, for any
$k\in{\mathbb{N}}^{*}$,
${\bf{d}}=(d_{0},\ldots,d_{k})\in({\mathbb{N}}^{*})^{k+1}$,
${\bf{t}}=(t_{0},\ldots,t_{k})\in({\mathbb{N}}^{*})^{k+1}$,
${\bm{\alpha}}=(\alpha_{0},\ldots,\alpha_{k})\in({\mathbb{R}}_{+}^{*})^{k+1}$
and a finite constant $B\geq 0$, we denote
${\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$ the class of functions
as,

$\displaystyle{\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)=$
$\displaystyle\left\\{f_{k}\circ\cdots\circ
f_{0},\;f_{i}=(f_{ij})_{j}:\left[{a_{i},b_{i}}\right]^{d_{i}}\rightarrow\left[{a_{i+1},b_{i+1}}\right]^{d_{i+1}},\right.$
(22)
$\displaystyle\quad\quad\left.f_{ij}\in{\mathcal{H}}^{\alpha_{i}}(\left[{a_{i},b_{i}}\right]^{t_{i}},B)\;\mbox{and
}(|a_{i}|\vee|b_{i}|)\leq B\right\\},$

where $a_{0}=0$, $b_{0}=1$, $d_{0}=d$ and $d_{k+1}=1$. In what follows, we
assume the existence of an underlying regression function
$f^{\star}=f_{k}\circ\cdots\circ
f_{0}\in{\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$ such that
$Q^{\star}=Q_{f^{\star}}$ (or at least $Q^{\star}$ is close to $Q_{f^{\star}}$
with respect to $\ell$), where the values of $k$, ${\bf{d}}$, ${\bf{t}}$ and
${\bm{\alpha}}$ are considered to be known. We will then proceed to construct
suitable networks for approximating the class
${\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$ and implement the
$\ell$-type estimation procedure to derive the final estimator
$Q_{\widehat{f}}$ of $Q^{\star}$.

In such a composition structure, the power of approximation based on the
neural network actually relies on the so-called effective smoothness indices,
which are defined as

$\alpha^{*}_{i}=\alpha_{i}\prod_{l=i+1}^{k}\left(\alpha_{l}\wedge
1\right),\quad\mbox{for }\ i\in\\{0,\ldots,k-1\\}$

and $\alpha^{*}_{k}=\alpha_{k}$. Based on Proposition 2 and the basic
operation rules of the neural networks, we establish the following result to
approximate any function belonging to
${\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$.

######  Proposition 3.

Assuming that $f\in{\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$ with
${\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$ defined by (22). For all
$i\in\\{0,\ldots,k\\}$, denote

$p_{i}=114(\lfloor\alpha_{i}\rfloor+1)^{2}3^{t_{i}}t_{i}^{\lfloor\alpha_{i}\rfloor+1}$

and

$L_{i}=21(\lfloor\alpha_{i}\rfloor+1)^{2}\lceil
n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil\lceil\log_{2}(8\lceil
n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil)\rceil+2t_{i}.$

There exists a function $\overline{f}$ implemented by a ReLU network with a
width of $\overline{p}=\max_{i\in\\{0,\ldots,k-1\\}}d_{i+1}p_{i}$ and a depth
of $\overline{L}=k+\sum_{i=0}^{k}L_{i}$ such that

$\displaystyle\|f-\overline{f}\|_{\infty}$
$\displaystyle\quad\leq(2B)^{1+\sum_{i=1}^{k}\alpha_{i}}\left(\prod_{i=0}^{k}\sqrt{d_{i}}\right)\left[{\sum_{i=0}^{k}C_{\alpha_{i},t_{i},B}^{\prod_{l=i+1}^{k}(\alpha_{l}\wedge
1)}(\lceil
n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil)^{-2\alpha^{*}_{i}/t_{i}}}\right],$

where

$C_{\alpha_{i},t_{i},B}=19(2B)^{\alpha_{i}+1}(\lfloor\alpha_{i}\rfloor+1)^{2}t_{i}^{\lfloor\alpha_{i}\rfloor+(\alpha_{i}\vee
1)/2}.$

The proof of Proposition 3 is postponed to Section 6.5. The presented
approximation result is notable for offering a well-defined structure for
neural networks to effectively implement diverse estimation approaches, as
compared to the sparsity-based networks considered in Schmidt-Hieber, (2020).
From this point of view, Proposition 3 is more informative. Building upon the
results of Theorem 1, Proposition 1, 3, and Lemma 3, we can derive the
following risk bound for the $\ell$-type estimators.

######  Corollary 2.

Assume that $f^{\star}\in{\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$
with ${\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$ defined by (22). For
all $i\in\\{0,\ldots,k\\}$, we set

$p_{i}=114(\lfloor\alpha_{i}\rfloor+1)^{2}3^{t_{i}}t_{i}^{\lfloor\alpha_{i}\rfloor+1}$

and

$L_{i}=21(\lfloor\alpha_{i}\rfloor+1)^{2}\lceil
n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil\lceil\log_{2}(8\lceil
n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil)\rceil+2t_{i}.$

Whatever the distribution of $W$, any $\ell$-type estimator
$\widehat{f}({\bm{X}})$ implemented by a ReLU neural network
${\mathcal{F}}_{(\overline{L},\overline{p},K)}$ with

$\overline{L}=k+\sum_{i=0}^{k}L_{i},\quad\quad\overline{p}=\max_{i=0,\ldots,k}d_{i+1}p_{i}$

and a sufficiently large $K$, satisfies that for all $n\geq
V(\overline{\mathcal{F}}_{(\overline{L},\overline{p})})$,

(23)
${\mathbb{E}}\left[{\ell\left({Q_{f^{\star}},Q_{\widehat{f}}}\right)}\right]\leq
C_{\epsilon,\sigma,k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B}\left(\sum_{i=0}^{k}n^{-\frac{\alpha_{i}^{*}}{t_{i}+2\alpha_{i}^{*}}}\right)(\log
n)^{3/2},$

where $C_{\epsilon,\sigma,k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B}$ is a numerical
constant depending on $\epsilon,\sigma,k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B$
only.

We left the proof of Corollary 2 to Section 6.6. Our comments are presented as
follows.

######  Remark 8.

Denoting

$\phi_{n}=\max_{i=0,\ldots,k}n^{-\alpha^{*}_{i}/(2\alpha^{*}_{i}+t_{i})},$

the result (23) we have established indicates that, up to a logarithmic term,
the $\ell$-type estimator $\widehat{f}$ based on the class
${\mathcal{F}}_{(\overline{L},\overline{p},K)}$ converges to the regression
function $f^{\star}$ at the rate of $\phi_{n}$. Furthermore, for sufficiently
large $n$ such that the right-hand side of (23) is smaller than 0.78, upon
applying Lemma 2, we obtain

${\mathbb{E}}\left[{\|f^{\star}-\widehat{f}\|_{1,P_{W}}}\right]\leq
C_{\epsilon,\sigma,k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B}\phi_{n}(\log
n)^{3/2}.$

This aligns with the risk bound established in Theorem 1 of Schmidt-Hieber,
(2020) for the least squares estimator with respect to the
${\mathbb{L}}_{2}(P_{W})$-norm.

######  Remark 9.

If the situation deviates from the ideal scenario where
$Q^{\star}=Q_{f^{\star}}$ and
$f^{\star}\in{\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$, a bias term
$\inf_{f\in{\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)}\ell(Q^{\star},Q_{f})$
will be included in the final risk bound (23). However, as long as the bias
term is not significantly larger than the quantity on the right-hand side of
(23), the accuracy of the resulting estimator $\widehat{f}$ remains on the
same order of magnitude as in the ideal case. This follows from the robustness
property of the $\ell$-type estimator as we have explained in Section 3.

The following lower bound demonstrates that the convergence rate $\phi_{n}$ is
minimax optimal, at least when $W$ is uniformly distributed on
$\left[{0,1}\right]^{d_{0}}$.

######  Theorem 2.

Let $P_{W}$ be the uniform distribution on $\left[{0,1}\right]^{d_{0}}$. For
any $k\in{\mathbb{N}}^{*}$, ${\bf{d}}\in({\mathbb{N}}^{*})^{k+1}$,
${\bf{t}}\in({\mathbb{N}}^{*})^{k+1}$ such that
$t_{j}\leq\min(d_{0},\ldots,d_{j-1})$ for all $j$, any
${\bm{\alpha}}\in({\mathbb{R}}_{+}^{*})^{k+1}$ and $B>0$ large enough, there
exists a positive constant $c$ such that

$\inf_{\widehat{f}}\sup_{f^{\star}\in{\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)}{\mathbb{E}}\left[{\ell\left({Q_{f^{\star}},Q_{\widehat{f}}}\right)}\right]\geq
c\phi_{n},$

where the infimum runs among all possible estimators of $f^{\star}$.

The proof of Theorem 2 is deferred to Section 6.7.

##  6\. Proofs

###  6.1. Proof of Lemma 1

###### Proof.

Drawing on the formulation of $t_{(f_{1},f_{2})}$ and the definition of
$\ell(\cdot,\cdot)$ as provided in (3), we can deduce that

$\displaystyle{\mathbb{E}}_{P^{\star}}\left[{t_{(f_{1},f_{2})}(W,Y)}\right]$
$\displaystyle=$
$\displaystyle\int_{{\mathscr{W}}}\left[{Q^{\star}_{(w)}\left(q_{f_{2}(w)}>q_{f_{1}(w)}\right)-Q_{f_{1}(w)}\left(q_{f_{2}(w)}>q_{f_{1}(w)}\right)}\right]dP_{W}(w)$
$\displaystyle\leq$
$\displaystyle\int_{{\mathscr{W}}}\|Q^{\star}_{(w)}-Q_{f_{1}(w)}\|_{TV}dP_{W}(w)$
$\displaystyle=$ $\displaystyle\ \ell(Q^{\star},Q_{f_{1}}),$

which gives the second inequality in (4). Furthermore, for any two
probabilities $P$ and $R$ on the measured space
$({\mathscr{X}},{\mathcal{X}})$, it is well known that the total variation
distance can equivalently be written as

$\|P-R\|_{TV}=R(r>p)-P(r>p),$

where $p$ and $r$ stand for the respective densities of $P$ and $R$ with
respect to some common dominating measure $\mu$. Given this fact, we can
calculate

$\displaystyle{\mathbb{E}}_{P^{\star}}\left[{t_{(f_{1},f_{2})}(W,Y)}\right]$
$\displaystyle=$
$\displaystyle\int_{{\mathscr{W}}}\left[{Q^{\star}_{(w)}\left(q_{f_{2}(w)}>q_{f_{1}(w)}\right)-Q_{f_{2}(w)}\left(q_{f_{2}(w)}>q_{f_{1}(w)}\right)}\right]dP_{W}(w)$
$\displaystyle+\int_{{\mathscr{W}}}\left[{Q_{f_{2}(w)}\left(q_{f_{2}(w)}>q_{f_{1}(w)}\right)-Q_{f_{1}(w)}\left(q_{f_{2}(w)}>q_{f_{1}(w)}\right)}\right]dP_{W}(w)$
$\displaystyle\geq$
$\displaystyle\int_{{\mathscr{W}}}\left[{\|Q_{f_{1}(w)}-Q_{f_{2}(w)}\|_{TV}-\|Q^{\star}_{(w)}-Q_{f_{2}(w)}\|_{TV}}\right]dP_{W}(w)$
$\displaystyle=$ $\displaystyle\
\ell(Q_{f_{1}},Q_{f_{2}})-\ell(Q^{\star},Q_{f_{2}}),$

which yields the first inequality in (4). ∎

###  6.2. Proof of Theorem 1

Prior to proving Theorem 1, we will initially establish several auxiliary
results that will serve as the foundation for deriving Theorem 1.

######  Proposition 4.

For any $\overline{f}\in{\mathcal{F}}$, we define

${\mathscr{C}}_{+}({\mathcal{F}},\overline{f})=\left\\{\left\\{(w,y)\in{\mathscr{W}}\times{\mathscr{Y}}\
s.t.\
q_{f(w)}(y)>q_{\overline{f}(w)}(y)\right\\},\;f\in{\mathcal{F}}\right\\}$

and

${\mathscr{C}}_{-}({\mathcal{F}},\overline{f})=\left\\{\left\\{(w,y)\in{\mathscr{W}}\times{\mathscr{Y}}\
s.t.\
q_{f(w)}(y)<q_{\overline{f}(w)}(y)\right\\},\;f\in{\mathcal{F}}\right\\}.$

Under Assumption 1, the classes of subsets
${\mathscr{C}}_{+}({\mathcal{F}},\overline{f})$ and
${\mathscr{C}}_{-}({\mathcal{F}},\overline{f})$ are both VC with dimensions
not larger than $9.41V$.

###### Proof.

We first prove the result holds for the class
${\mathscr{C}}_{+}({\mathcal{F}},\overline{f})$. For any $f\in{\mathcal{F}}$,
we define the function $\widetilde{q}_{f}$ on
${\mathscr{W}}\times{\mathscr{Y}}$ as

$\widetilde{q}_{f(w)}(y)=\exp\left[{\frac{yf(w)}{\sigma^{2}}-\frac{f^{2}(w)}{2\sigma^{2}}}\right].$

Then the class of subsets ${\mathscr{C}}_{+}({\mathcal{F}},\overline{f})$ can
be rewritten as

${\mathscr{C}}_{+}({\mathcal{F}},\overline{f})=\left\\{\left\\{(w,y)\in{\mathscr{W}}\times{\mathscr{Y}}\
s.t.\
\widetilde{q}_{f(w)}(y)>\widetilde{q}_{\overline{f}(w)}(y)\right\\},\;f\in{\mathcal{F}}\right\\}.$

We introduce the result of Proposition 5 in Baraud and Chen, (2020) as
follows.

######  Proposition 5.

Let $I\subset{\mathbb{R}}$ be a non-trivial interval and ${\mathcal{F}}$ a
class of functions from ${\mathscr{W}}$ into $I$. If ${\mathcal{F}}$ is VC-
subgraph on ${\mathscr{W}}$ with dimension not larger than $V$, the class of
functions

$\left\\{h_{f}:(w,y)\mapsto e^{S(y)f(w)-A(f(w))},\;f\in{\mathcal{F}}\right\\}$

is VC-subgraph on ${\mathscr{W}}\times{\mathscr{Y}}$ with dimension not larger
than $9.41V$, where $S$ is a real-valued measurable function on
${\mathscr{Y}}$ and $A$ is convex and continuous on $I$.

Note that function $\widetilde{q}_{f(w)}(y)$ takes a particular form as
described in Proposition 5 with $S(y)=y/\sigma^{2}$, for all
$y\in{\mathbb{R}}$, and $A(u)=u^{2}/(2\sigma^{2})$, for all
$u\in{\mathbb{R}}$. Therefore, under Assumption 1, the class of functions
$\left\\{\widetilde{q}_{f},\;f\in{\mathcal{F}}\right\\}$ on
${\mathscr{W}}\times{\mathscr{Y}}$ is VC-subgraph with dimension not larger
than $9.41V$. Moreover, since for any given function
$\overline{f}\in{\mathcal{F}}$, $\widetilde{q}_{\overline{f}}$ is a fixed
function taking its values in ${\mathbb{R}}$, applying Lemma 2.6.18 (v) of van
der Vaart and Wellner, (1996) (see also Proposition 42 (i) in Baraud et al.,
(2017)), we obtain that the class of functions
$\left\\{\widetilde{q}_{f}-\widetilde{q}_{\overline{f}},\;f\in{\mathcal{F}}\right\\}$
on ${\mathscr{W}}\times{\mathscr{Y}}$ is VC-subgraph with dimension not larger
than $9.41V$. According Proposition 2.1 of Baraud, (2016),
$\left\\{\widetilde{q}_{f}-\widetilde{q}_{\overline{f}},\;f\in{\mathcal{F}}\right\\}$
is weak VC-major with dimension not larger than $9.41V$, which implies that
the class of subsets

$\left\\{\left\\{(w,y)\in{\mathscr{W}}\times{\mathscr{Y}}\ s.t.\
\widetilde{q}_{f(w)}(y)-\widetilde{q}_{\overline{f}(w)}(y)>0\right\\},\;f\in{\mathcal{F}}\right\\}$

is a VC-class of subsets of ${\mathscr{W}}\times{\mathscr{Y}}$ with dimension
not larger than $9.41V$. Hence, the conclusion holds for
${\mathscr{C}}_{+}({\mathcal{F}},\overline{f})$.

Now we show the conclusion also holds for the class of subsets
${\mathscr{C}}_{-}({\mathcal{F}},\overline{f})$. As we have seen, under
Assumption 1, $\left\\{\widetilde{q}_{f},\;f\in{\mathcal{F}}\right\\}$ on
${\mathscr{W}}\times{\mathscr{Y}}$ is VC-subgraph with dimension not larger
than $9.41V$. By applying Proposition 42 (iii) of Baraud et al., (2017), we
can establish that $\\{-\widetilde{q}_{f},\;f\in{\mathcal{F}}\\}$ on
${\mathscr{W}}\times{\mathscr{Y}}$ is a VC-subgraph with dimension not
exceeding $9.41V$. As a result of Lemma 2.6.18 (v) of van der Vaart and
Wellner, (1996), this property also holds for the class
$\\{\widetilde{q}_{\overline{f}}-\widetilde{q}_{f},\;f\in{\mathcal{F}}\\}$ for
any fixed $\overline{f}\in{\mathcal{F}}$. Finally, we can conclude using a
similar argument as we did for
${\mathscr{C}}_{+}({\mathcal{F}},\overline{f})$. ∎

######  Proposition 6.

For any $\overline{f}\in{\mathcal{F}}$, we define

${\mathscr{C}}_{=}({\mathcal{F}},\overline{f})=\left\\{\\{w\in{\mathscr{W}}\
s.t.\ f(w)=\overline{f}(w)\\},\;f\in{\mathcal{F}}\right\\}.$

Under Assumption 1, the class of subsets
${\mathscr{C}}_{=}({\mathcal{F}},\overline{f})$ is a VC-class of sets on
${\mathscr{W}}$ with dimension not larger than $9.41V$.

###### Proof.

We set

${\mathscr{C}}_{\geq}({\mathcal{F}},\overline{f})=\left\\{\\{w\in{\mathscr{W}}\
s.t.\ f(w)-\overline{f}(w)\geq 0\\},\;f\in{\mathcal{F}}\right\\}$

and

${\mathscr{C}}_{\leq}({\mathcal{F}},\overline{f})=\left\\{\\{w\in{\mathscr{W}}\
s.t.\ f(w)-\overline{f}(w)\leq 0\\},\;f\in{\mathcal{F}}\right\\}.$

Since ${\mathcal{F}}$ is VC-subgraph on ${\mathscr{W}}$ with dimension not
larger than $V$ and $\overline{f}$ is a fixed function,
$\\{f-\overline{f},\;f\in{\mathcal{F}}\\}$ is VC-subgraph on ${\mathscr{W}}$
with dimension not larger than $V$ as a consequence of applying Proposition 42
(i) in Baraud et al., (2017). According to Proposition 2.1 of Baraud, (2016),
$\\{f-\overline{f},\;f\in{\mathcal{F}}\\}$ is weak VC-major with dimension not
larger than $V$, which implies that the class of subsets

$\left\\{\left\\{w\in{\mathscr{W}}\ s.t.\
f(w)>\overline{f}(w)\right\\},\;f\in{\mathcal{F}}\right\\}$

is a VC-class of subsets of ${\mathscr{W}}$ with dimension not larger than
$V$. Then Lemma 2.6.17 (i) of van der Vaart and Wellner, (1996) implies that
${\mathscr{C}}_{\leq}({\mathcal{F}},\overline{f})$ is a VC-class of subsets of
${\mathscr{W}}$ with dimension not larger than $V$. Following a similar
argument, we can show that the same conclusion also holds for the class
${\mathscr{C}}_{\geq}({\mathcal{F}},\overline{f})$.

Writing

${\mathscr{C}}_{\geq}({\mathcal{F}},\overline{f})\bigwedge{\mathscr{C}}_{\leq}({\mathcal{F}},\overline{f})=\left\\{C_{\geq}\cap
C_{\leq},\;C_{\geq}\in{\mathscr{C}}_{\geq}({\mathcal{F}},\overline{f}),\;C_{\leq}\in{\mathscr{C}}_{\leq}({\mathcal{F}},\overline{f})\right\\},$

we can deduce that
${\mathscr{C}}_{\geq}({\mathcal{F}},\overline{f})\bigwedge{\mathscr{C}}_{\leq}({\mathcal{F}},\overline{f})$
is a VC-class of subsets of ${\mathscr{W}}$ with dimension not larger than
$9.41V$ according to Theorem 1.1 of van der Vaart and Wellner, (2009). It is
easy to note that
${\mathscr{C}}_{=}({\mathcal{F}},\overline{f})\subset{\mathscr{C}}_{\geq}({\mathcal{F}},\overline{f})\bigwedge{\mathscr{C}}_{\leq}({\mathcal{F}},\overline{f})$,
which implies the completion of the proof. ∎

######  Lemma 4.

Under Assumption 1, whatever the conditional distributions
${\mathbf{Q}}^{\star}=(Q^{\star}_{1},\ldots,Q^{\star}_{n})$ of the $Y_{i}$
given $W_{i}$ and the distributions of $W_{i}$, any $\ell$-type estimator
$\widehat{f}$ based on the set ${\mathcal{F}}$ satisfies that for any
$\overline{f}\in{\mathcal{F}}$ and any $\xi>0$, with a probability at least
$1-e^{-\xi}$,

(24) $\ell({\mathbf{Q}}_{\overline{f}},{\mathbf{Q}}_{\widehat{f}})\leq
2\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+\frac{2\bm{\vartheta}(\overline{f})}{n}+\sqrt{\frac{8(\xi+\log
2)}{n}}+\frac{\epsilon}{n},$

where

$\displaystyle\bm{\vartheta}(\overline{f})=$
$\displaystyle{\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left[{{\mathbf{T}}_{l}({\bm{X}},\overline{f},f^{\prime})-{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},\overline{f},f^{\prime})}\right]}\right]}\right]$
$\displaystyle\vee{\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left[{{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},f^{\prime},\overline{f})}\right]-{\mathbf{T}}_{l}({\bm{X}},f^{\prime},\overline{f})}\right]}\right].$

###### Proof.

The proof of Lemma 4 builds upon the idea presented in the proof of Theorem 1
in Baraud et al., (2022), but with certain modifications to adapt it to the
regression setting.

For any $f_{1},f_{2}\in{\mathcal{F}}$, define

${\mathbf{Z}}_{+}({\bm{X}},f_{1})=\sup_{f_{2}\in{\mathcal{F}}}\left[{{\mathbf{T}}_{l}({\bm{X}},f_{1},f_{2})-{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},f_{1},f_{2})}\right]}\right]$
${\mathbf{Z}}_{-}({\bm{X}},f_{1})=\sup_{f_{2}\in{\mathcal{F}}}\left[{{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},f_{2},f_{1})}\right]-{\mathbf{T}}_{l}({\bm{X}},f_{2},f_{1})}\right]$

and set

${\mathbf{Z}}({\bm{X}},f_{1})={\mathbf{Z}}_{+}({\bm{X}},f_{1})\vee{\mathbf{Z}}_{-}({\bm{X}},f_{1}).$

As per Lemma 1, for any $f,\overline{f}\in{\mathcal{F}}$, it holds that

$\displaystyle n\ell({\mathbf{Q}}_{\overline{f}},{\mathbf{Q}}_{f})$
$\displaystyle\leq
n\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},f,\overline{f})}\right]$
$\displaystyle\leq
n\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},f,\overline{f})}\right]-{\mathbf{T}}_{l}({\bm{X}},f,\overline{f})+{\mathbf{T}}_{l}({\bm{X}},f,\overline{f})$
$\displaystyle\leq
n\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+{\mathbf{Z}}({\bm{X}},\overline{f})+{\mathbf{T}}_{l}({\bm{X}},f,\overline{f})$
(25) $\displaystyle\leq
n\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+{\mathbf{Z}}({\bm{X}},\overline{f})+{\mathbf{T}}_{l}({\bm{X}},f).$

By utilizing (25), substituting $f$ with
$\widehat{f}({\bm{X}})\in{\mathscr{E}}({\bm{X}},\epsilon)$, and employing the
definition of $\widehat{f}({\bm{X}})$, we can derive that

$\displaystyle n\ell({\mathbf{Q}}_{\overline{f}},{\mathbf{Q}}_{\widehat{f}})$
$\displaystyle\leq
n\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+{\mathbf{Z}}({\bm{X}},\overline{f})+{\mathbf{T}}_{l}({\bm{X}},\widehat{f})$
(26) $\displaystyle\leq
n\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+{\mathbf{Z}}({\bm{X}},\overline{f})+{\mathbf{T}}_{l}({\bm{X}},\overline{f})+\epsilon.$

Moreover, we can compute that

$\displaystyle{\mathbf{T}}_{l}({\bm{X}},\overline{f})$
$\displaystyle=\sup_{f\in{\mathcal{F}}}{\mathbf{T}}_{l}({\bm{X}},\overline{f},f)$
$\displaystyle\leq\sup_{f\in{\mathcal{F}}}\left[{{\mathbf{T}}_{l}({\bm{X}},\overline{f},f)-{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},\overline{f},f)}\right]}\right]+\sup_{f\in{\mathcal{F}}}{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},\overline{f},f)}\right]$
(27)
$\displaystyle\leq{\mathbf{Z}}({\bm{X}},\overline{f})+n\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}}),$

where the second inequality is obtained by applying Lemma 1. Combining (26)
and (27), we obtain that for any $\overline{f}\in{\mathcal{F}}$,

(28) $n\ell({\mathbf{Q}}_{\overline{f}},{\mathbf{Q}}_{\widehat{f}})\leq
2{\mathbf{Z}}({\bm{X}},\overline{f})+2n\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+\epsilon.$

In what follows, we study the term ${\mathbf{Z}}({\bm{X}},\overline{f})$ to
have a further insight of the risk bound for the estimator $\widehat{f}$. It
is worth noting that for any $\overline{f},f\in{\mathcal{F}}$ and
$(w,y),(w^{\prime},y^{\prime})\in{\mathscr{W}}\times{\mathscr{Y}}$, the
following inequality holds:

$\big{|}t_{(\overline{f},f)}(w,y)-t_{(\overline{f},f)}(w^{\prime},y^{\prime})\big{|}\leq
2.$

Writing $\bm{x}=(x_{1},\ldots,x_{n})\in{\mathscr{X}}^{n}$ and
$\bm{x}^{\prime}_{(i)}=(x_{1},\ldots,x^{\prime}_{i},\ldots,x_{n})\in{\mathscr{X}}^{n}$,
as an immediate consequence, we can derive that

$\frac{1}{2}\big{|}{\mathbf{Z}}_{+}(\bm{x},\overline{f})-{\mathbf{Z}}_{+}(\bm{x}^{\prime}_{(i)},\overline{f})\big{|}\leq
1.$

By following a similar approach as in the proof of Lemma 2 in Baraud, (2021)
and considering the term $\xi$ replaced with $\xi+\log 2$, one can conclude
that with a probability of at least $1-(1/2)e^{-\xi}$,

$\displaystyle{\mathbf{Z}}_{+}({\bm{X}},\overline{f})$
$\displaystyle\leq{\mathbb{E}}\left[{{\mathbf{Z}}_{+}({\bm{X}},\overline{f})}\right]+\sqrt{2n(\xi+\log
2)}$
$\displaystyle={\mathbb{E}}\left[{\sup_{f\in{\mathcal{F}}}\left[{{\mathbf{T}}_{l}({\bm{X}},\overline{f},f)-{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},\overline{f},f)}\right]}\right]}\right]+\sqrt{2n(\xi+\log
2)}$ (29) $\displaystyle\leq\bm{\vartheta}(\overline{f})+\sqrt{2n(\xi+\log
2)}.$

A similar argument gives that with a probability at least $1-(1/2)e^{-\xi}$,

(30)
${\mathbf{Z}}_{-}({\bm{X}},\overline{f})\leq\bm{\vartheta}(\overline{f})+\sqrt{2n(\xi+\log
2)}.$

By combining (29) and (30), we can derive that with a probability at least
$1-e^{-\xi}$,

(31)
${\mathbf{Z}}({\bm{X}},\overline{f})={\mathbf{Z}}_{+}({\bm{X}},\overline{f})\vee{\mathbf{Z}}_{-}({\bm{X}},\overline{f})\leq\bm{\vartheta}(\overline{f})+\sqrt{2n(\xi+\log
2)}.$

Finally, plugging (31) into (28) gives the upper bound

(32) $\ell({\mathbf{Q}}_{\overline{f}},{\mathbf{Q}}_{\widehat{f}})\leq
2\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+\frac{2\bm{\vartheta}(\overline{f})}{n}+\sqrt{\frac{8(\xi+\log
2)}{n}}+\frac{\epsilon}{n}.$

∎

######  Proposition 7.

Let $f_{1}$ and $f_{2}$ be two functions belonging to ${\mathcal{F}}$. For all
$w\in{\mathscr{W}}$, the following equality holds

$Q_{f_{1}(w)}(q_{f_{2}(w)}>q_{f_{1}(w)})=\Phi\left(-\frac{|f_{1}(w)-f_{2}(w)|}{2\sigma}\right)-\frac{1}{2}1\hskip-2.6pt{\rm
l}_{f_{1}(w)=f_{2}(w)},$

where $\Phi$ stands for the cumulative distribution function of the standard
normal distribution.

###### Proof.

For all $w\in{\mathscr{W}}$ satisfying $f_{1}(w)=f_{2}(w)$, it is easy to see
that $Q_{f_{1}(w)}(q_{f_{2}(w)}>q_{f_{1}(w)})=0$. The equality naturally holds
since

$\Phi\left(-\frac{|f_{1}(w)-f_{2}(w)|}{2\sigma}\right)-\frac{1}{2}1\hskip-2.6pt{\rm
l}_{f_{1}(w)=f_{2}(w)}=\Phi(0)-\frac{1}{2}=0.$

For all $w\in{\mathscr{W}}$ satisfying $f_{1}(w)>f_{2}(w)$,

$\displaystyle Q_{f_{1}(w)}(q_{f_{2}(w)}>q_{f_{1}(w)})$
$\displaystyle=\int_{-\infty}^{\left[{f_{1}(w)+f_{2}(w)}\right]/2}q_{f_{1}(w)}(y)dy$
$\displaystyle=\int_{-\infty}^{\left[{f_{2}(w)-f_{1}(w)}\right]/2\sigma}\frac{1}{\sqrt{2\pi}}e^{-\frac{t^{2}}{2}}dt$
$\displaystyle=\Phi\left(-\frac{|f_{1}(w)-f_{2}(w)|}{2\sigma}\right).$

For all $w\in{\mathscr{W}}$ satisfying $f_{1}(w)<f_{2}(w)$,

$\displaystyle Q_{f_{1}(w)}(q_{f_{2}(w)}>q_{f_{1}(w)})$
$\displaystyle=\int_{\left[{f_{1}(w)+f_{2}(w)}\right]/2}^{+\infty}q_{f_{1}(w)}(y)dy$
$\displaystyle=\int_{\left[{f_{2}(w)-f_{1}(w)}\right]/2\sigma}^{+\infty}\frac{1}{\sqrt{2\pi}}e^{-\frac{t^{2}}{2}}dt$
$\displaystyle=1-\Phi\left(\frac{f_{2}(w)-f_{1}(w)}{2\sigma}\right)$
$\displaystyle=\Phi\left(-\frac{|f_{1}(w)-f_{2}(w)|}{2\sigma}\right).$

Therefore, we can conclude the equality. ∎

The following result comes from the Proposition 3.1 in Baraud, (2016), and we
shall repeatedly use it in our proof.

######  Lemma 5.

Let $X_{1},\ldots,X_{n}$ be independent random variables with values in
$(E,{\mathcal{E}})$ and ${\mathcal{C}}$ a $VC$-class of subsets of $E$ with
$VC$-dimension not larger than $V\geq 1$ that satisfies for $\sigma\in(0,1]$,
$\sum_{i=1}^{n}{\mathbb{P}}(X_{i}\in C)\leq n\sigma^{2}$ for all
$C\in{\mathcal{C}}$. Then,

${\mathbb{E}}\left[{\sup_{C\in{\mathcal{C}}}\Big{|}\sum_{i=1}^{n}\left(1\hskip-2.6pt{\rm
l}_{C}(X_{i})-{\mathbb{P}}(X_{i}\in C)\right)\Big{|}}\right]\leq 10(\sigma\vee
a)\sqrt{nV\left[{5+\log\left(\frac{1}{\sigma\vee a}\right)}\right]}$

where

$a=\left[{32\sqrt{\frac{(V\wedge n)}{n}\log\left(\frac{2en}{V\wedge
n}\right)}}\right]\wedge 1.$

To prove Theorem 1, we also need the following result, which can be obtained
by making a modification to the proof of Theorem 2 in Baraud and Chen, (2020).

######  Lemma 6.

Let $W_{1},\ldots,W_{n}$ be $n$ independent random variables with values in
$({\mathscr{W}},{\mathcal{W}})$ and ${\mathcal{F}}$ an at most countable VC-
subgraph class of functions with values in $[0,1]$ and VC-dimension not larger
than $V\geq 1$. If

$Z({\mathcal{F}})=\sup\limits_{f\in{\mathcal{F}}}\left|\sum\limits_{i=1}^{n}(f(W_{i})-{\mathbb{E}}\left[{f(W_{i})}\right])\right|\;\;\text{and}\;\;\sup_{f\in{\mathcal{F}}}\frac{1}{n}\sum_{i=1}^{n}{\mathbb{E}}\left[{f^{2}(W_{i})}\right]\leq\sigma^{2}\leq
1,$

then

${\mathbb{E}}\left[{Z({\mathcal{F}})}\right]\leq
4.61\sqrt{nV\sigma^{2}{\mathcal{L}}(\sigma)}+85V{\mathcal{L}}(\sigma),$

with ${\mathcal{L}}(\sigma)=9.11+\log(1/\sigma^{2})$.

###### Proof of Theorem 1.

Now we will proceed to prove Theorem 1. Utilizing the result from Lemma 4, we
only need to establish an upper bound for the term
$\bm{\vartheta}(\overline{f})$. Let us express $\bm{\vartheta}(\overline{f})$
as
$\bm{\vartheta}(\overline{f})=\bm{\vartheta}_{1}(\overline{f})\vee\bm{\vartheta}_{2}(\overline{f})$,
where

$\bm{\vartheta}_{1}(\overline{f})={\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left[{{\mathbf{T}}_{l}({\bm{X}},\overline{f},f^{\prime})-{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},\overline{f},f^{\prime})}\right]}\right]}\right]$

and

$\bm{\vartheta}_{2}(\overline{f})={\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left[{{\mathbb{E}}\left[{{\mathbf{T}}_{l}({\bm{X}},f^{\prime},\overline{f})}\right]-{\mathbf{T}}_{l}({\bm{X}},f^{\prime},\overline{f})}\right]}\right].$

In what follows, we will derive an upper bound for the term
$\bm{\vartheta}_{1}(\overline{f})$.

For any $f_{1},f_{2}\in{\mathcal{F}}$, define

$g_{(f_{1},f_{2})}(w,y)=1\hskip-2.6pt{\rm
l}_{q_{f_{2}(w)}(y)>q_{f_{1}(w)}(y)},\quad\mbox{for all}\
(w,y)\in{\mathscr{W}}\times{\mathscr{Y}}.$

Let $\Phi$ be the cumulative distribution function of the standard normal
distribution. For any $f_{1},f_{2}\in{\mathcal{F}}$, define

$h_{(f_{1},f_{2})}(w)=\Phi\left(-\frac{|f_{1}(w)-f_{2}(w)|}{2\sigma}\right),\quad\mbox{for
all}\ w\in{\mathscr{W}}$

and

$k_{(f_{1},f_{2})}(w)=\frac{1}{2}1\hskip-2.6pt{\rm
l}_{f_{1}(w)=f_{2}(w)},\quad\mbox{for all}\ w\in{\mathscr{W}}.$

Given any $f_{1},f_{2}\in{\mathcal{F}}$, according to Proposition 7, we have
that for all $(w,y)\in{\mathscr{W}}\times{\mathscr{Y}}$,

$\displaystyle t_{(f_{1},f_{2})}(w,y)$
$\displaystyle=g_{(f_{1},f_{2})}(w,y)-\left[{h_{(f_{1},f_{2})}(w)-k_{(f_{1},f_{2})}(w)}\right]$
(33)
$\displaystyle=g_{(f_{1},f_{2})}(w,y)-h_{(f_{1},f_{2})}(w)+k_{(f_{1},f_{2})}(w).$

By the definition of ${\mathbf{T}}_{l}$ and the equality (33), we deduce that

$\displaystyle\bm{\vartheta}_{1}(\overline{f})=$ $\displaystyle\
{\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left[{\sum_{i=1}^{n}\left(t_{(\overline{f},f^{\prime})}(W_{i},Y_{i})-{\mathbb{E}}\left[{t_{(\overline{f},f^{\prime})}(W_{i},Y_{i})}\right]\right)}\right]}\right]$
$\displaystyle\leq$ $\displaystyle\
{\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left|\sum_{i=1}^{n}\left(g_{(\overline{f},f^{\prime})}(W_{i},Y_{i})-{\mathbb{E}}\left[{g_{(\overline{f},f^{\prime})}(W_{i},Y_{i})}\right]\right)\right|}\right]$
$\displaystyle+{\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left|\sum_{i=1}^{n}\left(h_{(\overline{f},f^{\prime})}(W_{i})-{\mathbb{E}}\left[{h_{(\overline{f},f^{\prime})}(W_{i})}\right]\right)\right|}\right]$
$\displaystyle+{\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left|\sum_{i=1}^{n}\left(k_{(\overline{f},f^{\prime})}(W_{i})-{\mathbb{E}}\left[{k_{(\overline{f},f^{\prime})}(W_{i})}\right]\right)\right|}\right].$

As it has been shown in Proposition 4 that under Assumption 1, the class of
subset ${\mathscr{C}}_{+}({\mathcal{F}},\overline{f})$ is VC with dimension
not larger than $9.41V$. Hence, applying Lemma 5 with $\sigma=1$, we can
obtain that

(34)
${\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left|\sum_{i=1}^{n}\left(g_{(\overline{f},f^{\prime})}(W_{i},Y_{i})-{\mathbb{E}}\left[{g_{(\overline{f},f^{\prime})}(W_{i},Y_{i})}\right]\right)\right|}\right]\leq
68.6\sqrt{nV}.$

According to Proposition 6, under Assumption 1, the class of subsets
${\mathscr{C}}_{=}({\mathcal{F}},\overline{f})$ is VC on ${\mathscr{W}}$ with
dimension not larger than $9.41V$. Applying Lemma 5 again, we derive that

(35)
${\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left|\sum_{i=1}^{n}\left(k_{(\overline{f},f^{\prime})}(W_{i})-{\mathbb{E}}\left[{k_{(\overline{f},f^{\prime})}(W_{i})}\right]\right)\right|}\right]\leq
34.3\sqrt{nV}.$

Moreover, under Assumption 1, the class of functions
$\\{f^{\prime}-\overline{f},\;f^{\prime}\in{\mathcal{F}}\\}$ is VC-subgraph on
${\mathscr{W}}$ with dimension not larger than $V$. Given the value of
$\sigma>0$, since the function $\psi(z)=-|z|/2\sigma$, for all
$z\in{\mathbb{R}}$ is unimodal, the class
$\\{\psi\circ(f^{\prime}-\overline{f}),\;f^{\prime}\in{\mathcal{F}}\\}$ is VC-
subgraph on ${\mathscr{W}}$ with dimension not larger than $9.41V$, as stated
in Proposition 42 (vi) of Baraud et al., (2017). Then according to Proposition
42 (ii) of Baraud et al., (2017),
$\\{h_{(\overline{f},f^{\prime})},\;f^{\prime}\in{\mathcal{F}}\\}=\\{\Phi\circ\left[{\psi\circ(f^{\prime}-\overline{f})}\right],\;f^{\prime}\in{\mathcal{F}}\\}$
is VC-subgraph on ${\mathscr{W}}$ with dimension not larger than $9.41V$.

It is easy to note that for any $f^{\prime}\in{\mathcal{F}}$,

$\frac{1}{n}\sum_{i=1}^{n}{\mathbb{E}}\left[{h_{(\overline{f},f^{\prime})}^{2}(W_{i})}\right]\leq
1.$

Applying Lemma 6 to the class
$\\{h_{(\overline{f},f^{\prime})},\;f^{\prime}\in{\mathcal{F}}\\}$ gives the
result that

(36)
${\mathbb{E}}\left[{\sup_{f^{\prime}\in{\mathcal{F}}}\left|\sum_{i=1}^{n}\left(h_{(\overline{f},f^{\prime})}(W_{i})-{\mathbb{E}}\left[{h_{(\overline{f},f^{\prime})}(W_{i})}\right]\right)\right|}\right]\leq
42.7\sqrt{nV}+7286.7V.$

Combining (34), (35) and (36) together, we can conclude that for any
$\overline{f}\in{\mathcal{F}}$

(37) $\bm{\vartheta}_{1}(\overline{f})\leq 145.6\sqrt{nV}+7286.7V.$

By following a similar line of proof, one can also derive that

(38) $\bm{\vartheta}_{2}(\overline{f})\leq 145.6\sqrt{nV}+7286.7V.$

Therefore, (37) and (38) together imply that for any
$\overline{f}\in{\mathcal{F}}$,

(39)
$\bm{\vartheta}(\overline{f})=\bm{\vartheta}_{1}(\overline{f})\vee\bm{\vartheta}_{2}(\overline{f})\leq
145.6\sqrt{nV}+7286.7V.$

By substituting the bound (39) into equation (24), we infer that for any
$\overline{f}\in{\mathcal{F}}$ and any $\xi>0$, with a probability at least
$1-e^{-\xi}$,

(40) $\ell({\mathbf{Q}}_{\overline{f}},{\mathbf{Q}}_{\widehat{f}})\leq
2\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+291.2\sqrt{\frac{V}{n}}+14573.4\frac{V}{n}+\sqrt{\frac{8(\xi+\log
2)}{n}}+\frac{\epsilon}{n},$

which concludes the inequality (5). Using the triangle inequality,

$\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\widehat{f}})\leq\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\overline{f}})+\ell({\mathbf{Q}}_{\overline{f}},{\mathbf{Q}}_{\widehat{f}}),$

we derive that any $\ell$-type estimator $\widehat{f}$ on the set
${\mathcal{F}}$ satisfies that for all $\xi>0$, with a probability at least
$1-e^{-\xi}$,

$\ell({\mathbf{Q}}^{\star},{\mathbf{Q}}_{\widehat{f}})\leq
3\ell({\mathbf{Q}}^{\star},{\mathscrbf{Q}})+291.2\sqrt{\frac{V}{n}}+14573.4\frac{V}{n}+\sqrt{\frac{8(\xi+\log
2)}{n}}+\frac{\epsilon}{n}.$

∎

###  6.3. Proof of Lemma 3

###### Proof.

Lemma 3 can be proven using a similar argument as in the proof of Lemma 11 in
Chen, (2022), where the main idea is inspired by the proof of Lemma 5 of
Schmidt-Hieber, (2020). We only need to show that for any
$f\in\overline{\mathcal{F}}_{(L,{\bm{p}},K)}$, there exists a sequence of
functions $f_{i}\in{\mathcal{F}}_{(L,{\bm{p}},K)}$, $i\in{\mathbb{N}}^{*}$
such that

$\lim_{i\rightarrow+\infty}\|f-f_{i}\|_{\infty}=0.$

For any $f\in\overline{\mathcal{F}}_{(L,{\bm{p}},K)}$, recall that it can be
written as

$f({\bm{w}})=M_{L}\circ\sigma\circ M_{L-1}\circ\cdots\circ\sigma\circ
M_{0}({\bm{w}})\quad\mbox{for any\ }{\bm{w}}\in\left[{0,1}\right]^{d},$

where

$M_{l}({\bm{y}})=A_{l}({\bm{y}})+b_{l},\mbox{\quad for\ }l=0,\ldots,L,$

$A_{l}$ is a $p_{l+1}\times p_{l}$ weight matrix and the shift vector $b_{l}$
is of size $p_{l+1}$ for any $l\in\\{0,\ldots,L\\}$.

For $l\in\\{1,\ldots,L\\}$, we define the function
$f_{l}^{+}:\left[{0,1}\right]^{d}\rightarrow{\mathbb{R}}^{p_{l}}$,

$f_{l}^{+}({\bm{w}})=\sigma\circ M_{l-1}\circ\cdots\circ\sigma\circ
M_{0}({\bm{w}})$

and for $l\in\\{1,\ldots,L+1\\}$, we define
$f_{l}^{-}:{\mathbb{R}}^{p_{l-1}}\rightarrow{\mathbb{R}}$

$f_{l}^{-}({\bm{x}})=M_{L}\circ\sigma\circ\cdots\circ\sigma\circ
M_{l-1}({\bm{x}}).$

We set the notations $f_{0}^{+}({\bm{x}})=f_{L+2}^{-}({\bm{x}})={\bm{x}}$.
Given a vector ${\bm{v}}=(v_{1},\ldots,v_{p})^{\top}$ of any size
$p\in{\mathbb{N}}^{*}$, we denote
$|{\bm{v}}|_{\infty}=\max_{i=1,\ldots,p}|v_{i}|$.

For any $f\in\overline{\mathcal{F}}_{(L,{\bm{p}},K)}$, with the fact that the
absolute values of all the parameters are bounded by $K$ and
${\bm{w}}\in\left[{0,1}\right]^{d}$, we have for all $l\in\\{1,\ldots,L\\}$

$\left|f_{l}^{+}({\bm{w}})\right|_{\infty}\leq
K_{+}^{l}\prod_{k=0}^{l-1}(p_{k}+1),$

where $K_{+}=\max\\{K,1\\}$, and $f_{l}^{-}$, $l\in\\{1,\ldots,L+1\\}$, is a
multivariate Lipschitz function with Lipschitz constant bounded by
$\prod_{k=l-1}^{L}(K_{+}p_{k})$.

For any $f\in\overline{\mathcal{F}}_{(L,{\bm{p}},K)}$ with weight matrices and
shift vectors $\\{M_{l}=(A_{l},b_{l})\\}_{l=0}^{L}$ and for all $\epsilon>0$,
since ${\mathbb{Q}}$ is dense in ${\mathbb{R}}$, there exist a
$N_{\epsilon}>0$ such that for all $i\geq N_{\epsilon}$, all the non-zero
parameters in $f_{i}\in{\mathcal{F}}_{(L,{\bm{p}},K)}$ are smaller than

$\frac{\epsilon}{(L+1)\prod_{k=0}^{L+1}\left[{K_{+}(p_{k}+1)}\right]}$

away from the corresponding ones in $f$. We denote the weight matrices and
shift vectors of function $f_{i}$ as
$\\{M_{l}^{i}=(A_{l}^{i},b_{l}^{i})\\}_{l=0}^{L}$. We note that

$f_{i}({\bm{w}})=f_{i,2}^{-}\circ\sigma\circ M^{i}_{0}\circ
f_{0}^{+}({\bm{w}})$

and

$f({\bm{w}})=f_{i,L+2}^{-}\circ M_{L}\circ f_{L}^{+}({\bm{w}}).$

Therefore, for all $i\geq N_{\epsilon}$ and all
${\bm{w}}\in\left[{0,1}\right]^{d}$

$\displaystyle\left|f_{i}({\bm{w}})-f({\bm{w}})\right|\leq$
$\displaystyle\sum_{l=1}^{L}\left|f_{i,l+1}^{-}\circ\sigma\circ
M^{i}_{l-1}\circ f_{l-1}^{+}({\bm{w}})-f_{i,l+1}^{-}\circ\sigma\circ
M_{l-1}\circ f_{l-1}^{+}({\bm{w}})\right|$ $\displaystyle+\left|M_{L}^{i}\circ
f_{L}^{+}({\bm{w}})-M_{L}\circ f_{L}^{+}({\bm{w}})\right|$ $\displaystyle\leq$
$\displaystyle\sum_{l=1}^{L}\left[{\prod_{k=l}^{L}K_{+}p_{k}}\right]\left|M^{i}_{l-1}\circ
f_{l-1}^{+}({\bm{w}})-M_{l-1}\circ f_{l-1}^{+}({\bm{w}})\right|_{\infty}$
$\displaystyle+\left|M_{L}^{i}\circ f_{L}^{+}({\bm{w}})-M_{L}\circ
f_{L}^{+}({\bm{w}})\right|$ $\displaystyle\leq$
$\displaystyle\sum_{l=1}^{L+1}\left[{\prod_{k=l}^{L+1}K_{+}p_{k}}\right]\left|M^{i}_{l-1}\circ
f_{l-1}^{+}({\bm{w}})-M_{l-1}\circ f_{l-1}^{+}({\bm{w}})\right|_{\infty}$
$\displaystyle\leq$
$\displaystyle\sum_{l=1}^{L+1}\left[{\prod_{k=l}^{L+1}K_{+}p_{k}}\right]\left[{\left|\left(A^{i}_{l-1}-A_{l-1}\right)\circ
f_{l-1}^{+}({\bm{w}})\right|_{\infty}+|b^{i}_{l-1}-b_{l-1}|_{\infty}}\right]$
$\displaystyle<$
$\displaystyle\frac{\sum_{l=1}^{L+1}\left[{\prod_{k=l}^{L+1}K_{+}p_{k}}\right]\left(p_{l-1}\left|f_{l-1}^{+}({\bm{w}})\right|_{\infty}+1\right)}{(L+1)\prod_{k=0}^{L+1}\left[{K_{+}(p_{k}+1)}\right]}\epsilon$
$\displaystyle<$ $\displaystyle\epsilon.$

Hence, by the definition we can conclude that ${\mathcal{F}}_{(L,{\bm{p}},K)}$
is dense in $\overline{\mathcal{F}}_{(L,{\bm{p}},K)}$ with respect to the
supremum norm $\|\cdot\|_{\infty}$.

∎

###  6.4. Proof of Corollary 1

###### Proof.

Recall that, in accordance with the general result (7), for any $n\geq
V(\overline{\mathcal{F}}_{(L,p)})\geq V(\overline{\mathcal{F}}_{(L,p,K)})$, we
can obtain

(41) ${\mathbb{E}}\left[{\ell(Q_{f^{\star}},Q_{\widehat{f}})}\right]\leq
C_{\epsilon}\left[{\inf_{f\in{\mathcal{F}}_{(L,p,K)}}\ell(Q_{f^{\star}},Q_{f})+\sqrt{\frac{V(\overline{\mathcal{F}}_{(L,p,K)})}{n}}}\right],$

where $C_{\epsilon}>0$ is a numerical constant depending on $\epsilon$ only.
Then, applying Lemma 3 and inequality (11), we derive from (41) that

$\displaystyle{\mathbb{E}}\left[{\ell(Q_{f^{\star}},Q_{\widehat{f}})}\right]$
$\displaystyle\leq
C_{\epsilon,\sigma}\left[{\inf_{f\in{\mathcal{F}}_{(L,p,K)}}\|f^{\star}-f\|_{1,P_{W}}+\sqrt{\frac{V(\overline{\mathcal{F}}_{(L,p,K)})}{n}}}\right]$
(42) $\displaystyle\leq
C_{\epsilon,\sigma}\left[{\inf_{f\in\overline{\mathcal{F}}_{(L,p,K)}}\|f^{\star}-f\|_{1,P_{W}}+\sqrt{\frac{V(\overline{\mathcal{F}}_{(L,p,K)})}{n}}}\right],$

where $C_{\epsilon,\sigma}$ is a numerical constant depending only on
$\epsilon$ and $\sigma$. On the one hand, as a consequence of Proposition 2,
we have that for the network $\overline{\mathcal{F}}_{(L,p,K)}$ with

(43)
$p=38(\lfloor\alpha\rfloor+1)^{2}3^{d}d^{\lfloor\alpha\rfloor+1}N\lceil\log_{2}(8N)\rceil,$
(44) $L=21(\lfloor\alpha\rfloor+1)^{2}M\lceil\log_{2}(8M)\rceil+2d$

and $K$ being large enough,

$\displaystyle\inf_{f\in\overline{\mathcal{F}}_{(L,p,K)}}\|f^{\star}-f\|_{1,P_{W}}$
$\displaystyle=\inf_{f\in\overline{\mathcal{F}}_{(L,p,K)}}\int_{{\mathscr{W}}}|f^{\star}(w)-f(w)|dP_{W}(w)$
(45) $\displaystyle\leq
19B(\lfloor\alpha\rfloor+1)^{2}d^{\lfloor\alpha\rfloor+(\alpha\vee
1)/2}(NM)^{-2\alpha/d}.$

On the other hand, given the equalities (43) and (44), we have $p\geq 342$ and
$L\geq 65$, for any $\alpha\in{\mathbb{R}}_{+}^{*}$. By applying Proposition
1, we can derive through a basic computation that

$\displaystyle V(\overline{\mathcal{F}}_{(L,p,K)})$
$\displaystyle\leq(L+1)\left(s+1\right)\log_{2}\left[{2\left(2e(L+1)\left(\frac{pL}{2}+1\right)\right)^{2}}\right]$
$\displaystyle\leq C_{d}p^{2}L^{2}\log_{2}\left(pL^{2}\right)$ (46)
$\displaystyle\leq
C_{\alpha,d}(NM)^{2}\left[{\log_{2}(2N)\log_{2}(2M)}\right]^{3},$

where $C_{d}$ only depends on $d$ and $C_{\alpha,d}$ only depends on $d$ and
$\alpha$. Plugging (6.4) and (6.4) into (42), we can conclude that

${\mathbb{E}}\left[{\ell(Q_{f^{\star}},Q_{\widehat{f}})}\right]\leq
C_{\epsilon,\sigma,\alpha,d,B}\left[{(NM)^{-2\alpha/d}+\frac{NM}{\sqrt{n}}\left(\log_{2}(2N)\log_{2}(2M)\right)^{3/2}}\right],$

where $C_{\epsilon,\sigma,\alpha,d,B}>0$ only depends on
$\epsilon,\sigma,\alpha,d$ and $B$. ∎

###  6.5. Proof of Proposition 3

###### Proof.

Prior to proving Proposition 3, we will first introduce the following rules
for network combination, which are extensively detailed in Section 7.1 of
Schmidt-Hieber, (2020).

Composition: Let $f_{1}\in\overline{\mathcal{F}}(L,{\bm{p}})$ and
$f_{2}\in\overline{\mathcal{F}}(L^{\prime},{\bm{p}}^{\prime})$ be such that
$p_{L+1}=p_{0}^{\prime}$. Let ${\bm{v}}\in{\mathbb{R}}^{p_{L+1}}$ be a vector.
We define the composed network $f_{2}\circ\sigma_{\bm{v}}(f_{1})$, where

$\sigma_{\bm{v}}\begin{pmatrix}y_{1}\\\ \vdots\\\
y_{p_{L+1}}\end{pmatrix}=\begin{pmatrix}\sigma(y_{1}-v_{1})\\\ \vdots\\\
\sigma(y_{p_{L+1}}-v_{p_{L+1}})\end{pmatrix},$

for any vector
${\bm{y}}=(y_{1},\ldots,y_{p_{L+1}})^{\top}\in{\mathbb{R}}^{p_{L+1}}$. Then
$f_{2}\circ\sigma_{\bm{v}}(f_{1})$ belongs to the space
$\overline{\mathcal{F}}(L+L^{\prime}+1,({\bm{p}},p^{\prime}_{1},\ldots,p^{\prime}_{L+1}))$.

Parallelization: Let $f_{1}$ and $f_{2}$ be two networks with an equal number
of hidden layers and identical input dimensions. Specifically, let
$f_{1}\in\overline{\mathcal{F}}(L,{\bm{p}})$ and
$f_{2}\in\overline{\mathcal{F}}(L,{\bm{p}}^{\prime})$, where
$p_{0}=p^{\prime}_{0}$. The parallelized network $(f_{1},f_{2})$ concurrently
computes $f_{1}$ and $f_{2}$ within a joint network belonging to the class
$\overline{\mathcal{F}}(L,(p_{0},p_{1}+p^{\prime}_{1},\ldots,p_{L+1}+p^{\prime}_{L+1}))$.

We will also use the following inequality later in the proof. It can be
derived through a minor modification of the proof of Lemma 3 in Schmidt-
Hieber, (2020).

######  Lemma 7.

Let $k\in{\mathbb{N}}^{*}$,
${\bf{d}}=(d_{0},\ldots,d_{k})\in({\mathbb{N}}^{*})^{k+1}$,
${\bf{t}}=(t_{0},\ldots,t_{k})\in({\mathbb{N}}^{*})^{k+1}$ with $t_{i}\leq
d_{i}$ and
${\bm{\alpha}}=(\alpha_{0},\ldots,\alpha_{k})\in({\mathbb{R}}_{+}^{*})^{k+1}$.
For any $i\in\\{0,\ldots,k\\}$ and $j\in\\{1,\ldots,d_{i+1}\\}$ with
$d_{k+1}=1$, let
$h_{ij}\in{\mathcal{H}}^{\alpha_{i}}(\left[{0,1}\right]^{t_{i}},Q_{i})$ taking
values in $\left[{0,1}\right]$ for some $Q_{i}\geq 1$ and
$h_{i}=(h_{i1},\ldots,h_{id_{i+1}})^{\top}$. Then for any function
$\widetilde{h}_{i}=(\widetilde{h}_{i1},\ldots,\widetilde{h}_{id_{i+1}})^{\top}$
with
$\widetilde{h}_{ij}:\left[{0,1}\right]^{t_{i}}\rightarrow\left[{0,1}\right]$,

$\|h_{k}\circ\cdots\circ
h_{0}-\widetilde{h}_{k}\circ\cdots\circ\widetilde{h}_{0}\|_{\infty}\leq\left(\prod_{i=0}^{k}Q_{i}\sqrt{d_{i}}\right)\sum_{i=0}^{k}|||h_{i}-\widetilde{h}_{i}|||_{\infty}^{\prod_{l=i+1}^{k}(\alpha_{l}\wedge
1)},$

where $|||f|||_{\infty}$ denotes the sup-norm of the function
${\bm{x}}\mapsto|f({\bm{x}})|_{\infty}$.

The essential strategy for establishing Proposition 3 is derived from a
section of the proof of Theorem 1 in Schmidt-Hieber, (2020). However, we
employ distinct fundamental networks as suggested by Proposition 2 to
approximate functions with Hölder smoothness. This, in turn, leads to more
specific neural network structures for approximating
$f^{\star}=f_{k}\circ\cdots\circ f_{0}$ compared to the sparsity-based
networks considered in Theorem 1 of Schmidt-Hieber, (2020).

To begin with, we rewrite

$f^{\star}=f_{k}\circ\cdots\circ f_{0}=g_{k}\circ\cdots\circ g_{0},$

where

$g_{0}:=\frac{f_{0}}{2B}+\frac{1}{2},\quad g_{k}:=f_{k}(2B\cdot-B)$

and

$g_{i}:=\frac{f_{i}(2B\cdot-B)}{2B}+\frac{1}{2}\quad\mbox{for all\
}i\in\\{1,\ldots,k-1\\}.$

Given the condition $B\geq 1$, we can readily confirm that
$g_{0j}\in{\mathcal{H}}^{\alpha_{0}}(\left[{0,1}\right]^{t_{0}},Q_{0})$,
$g_{ij}\in{\mathcal{H}}^{\alpha_{i}}(\left[{0,1}\right]^{t_{i}},Q_{i})$, for
$i\in\\{1,\ldots,k-1\\}$ and
$g_{kj}\in{\mathcal{H}}^{\alpha_{k}}(\left[{0,1}\right]^{t_{k}},Q_{k})$, with
$Q_{0}=1$, $Q_{i}=(2B)^{\alpha_{i}}$, for $i\in\\{1,\ldots,k-1\\}$ and
$Q_{k}=2^{\alpha_{k}}B^{\alpha_{k}+1}$.

We apply Proposition 2 to approximate each function $g_{ij}$, for all
$j\in\\{1,\ldots,d_{i+1}\\}$, $i\in\\{0,\ldots,k\\}$. In particular, for all
the functions $g_{i1},\ldots,g_{id_{i+1}}$, we take $N_{i}=1$, $M_{i}=\lceil
n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil$ and consider a ReLU network
$\overline{\mathcal{F}}_{(L_{i},(t_{i},p_{i},\ldots,p_{i},1))}$ with

$p_{i}=114(\lfloor\alpha_{i}\rfloor+1)^{2}3^{t_{i}}t_{i}^{\lfloor\alpha_{i}\rfloor+1},$
$L_{i}=21(\lfloor\alpha_{i}\rfloor+1)^{2}\lceil
n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil\lceil\log_{2}(8\lceil
n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil)\rceil+2t_{i}.$

According to Proposition 2, there exists a function
$\overline{g}_{ij}\in\overline{\mathcal{F}}_{(L_{i},(t_{i},p_{i},\ldots,p_{i},1))}$
such that

$\displaystyle\|\overline{g}_{ij}-g_{ij}\|_{\infty}$ $\displaystyle\leq
19Q_{i}(\lfloor\alpha_{i}\rfloor+1)^{2}t_{i}^{\lfloor\alpha_{i}\rfloor+(\alpha_{i}\vee
1)/2}(N_{i}M_{i})^{-2\alpha_{i}/t_{i}},$ (47) $\displaystyle\leq
19Q_{i}(\lfloor\alpha_{i}\rfloor+1)^{2}t_{i}^{\lfloor\alpha_{i}\rfloor+(\alpha_{i}\vee
1)/2}(\lceil n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil)^{-2\alpha_{i}/t_{i}}.$

Let $\widetilde{g}_{ij}=(\overline{g}_{ij}\vee 0)\wedge
1=1-(1-\overline{g}_{ij})_{+}$. It is straightforward to observe that
$\widetilde{g}_{ij}$ assumes values in the interval $\left[{0,1}\right]$.
Recall that since
$\overline{g}_{ij}\in\overline{\mathcal{F}}_{(L_{i},(t_{i},p_{i},\ldots,p_{i},1))}$,
it can be written as

$\overline{g}_{ij}=\overline{M}^{(i)}_{L_{i}}\circ\sigma\circ\cdots\circ\sigma\circ\overline{M}^{(i)}_{0},$

for some linear transformations
$\overline{M}^{(i)}_{0},\ldots,\overline{M}^{(i)}_{L_{i}}$. Let
$M_{L_{i}+2}(x)=M_{L_{i}+1}(x)=1-x$, for any $x\in{\mathbb{R}}$. Then we have

$\displaystyle\widetilde{g}_{ij}$ $\displaystyle=M_{L_{i}+2}\circ\sigma\circ
M_{L_{i}+1}\overline{g}_{ij}$ $\displaystyle=M_{L_{i}+2}\circ\sigma\circ
M_{L_{i}+1}\overline{M}^{(i)}_{L_{i}}\circ\sigma\circ\cdots\circ\sigma\circ\overline{M}^{(i)}_{0}$
$\displaystyle=M_{L_{i}+2}\circ\sigma\circ\widetilde{M}^{(i)}_{L_{i}}\circ\sigma\circ\cdots\circ\sigma\circ\overline{M}^{(i)}_{0}$

where
$\widetilde{M}^{(i)}_{L_{i}}=M_{L_{i}+1}\circ\overline{M}^{(i)}_{L_{i}}$.
Hence, we deduce that
$\widetilde{g}_{ij}\in\overline{\mathcal{F}}_{(L_{i}+1,(t_{i},p_{i},\ldots,p_{i},1,1))}$.
Furthermore, as each function $g_{ij}$ assumes values in the interval
$\left[{0,1}\right]$ due to the transformation, this implies that

(48)
$\|\sigma(\widetilde{g}_{ij})-g_{ij}\|_{\infty}=\|\widetilde{g}_{ij}-g_{ij}\|_{\infty}\leq\|\overline{g}_{ij}-g_{ij}\|_{\infty}.$

Next, we amalgamate these individual small networks by employing the
fundamental operations of neural networks introduced at the outset of this
proof. Note that
$\overline{\mathcal{F}}_{(L_{i}+1,(t_{i},p_{i},\ldots,p_{i},1,1))}\subset\overline{\mathcal{F}}_{(L_{i}+1,(d_{i},p_{i},\ldots,p_{i},1,1))}$,
for $t_{i}\leq d_{i}$. By the parallelization rule, the function
$\widetilde{g}_{i}=(\widetilde{g}_{i1},\ldots,\widetilde{g}_{id_{i+1}})$ can
be implemented by the ReLU neural network
$\overline{\mathcal{F}}_{(L_{i}+1,(d_{i},d_{i+1}p_{i},\ldots,d_{i+1}p_{i},d_{i+1},d_{i+1}))}$.
A similar analysis implies that $\overline{g}_{k}$ can be implemented by the
ReLU neural network
$\overline{\mathcal{F}}_{(L_{k},(d_{k},d_{k+1}p_{k},\ldots,d_{k+1}p_{k},d_{k+1}))}$.
To construct the function
$\widetilde{f}=\overline{g}_{k}\circ\widetilde{g}_{k-1}\cdots\circ\widetilde{g}_{0}$
that approximates the function $f^{\star}=g_{k}\circ\cdots\circ g_{0}$, we
apply the composition rule to amalgamate the networks we have considered
earlier. It can be shown with a similar argument as we did before that for any
$k\in{\mathbb{N}}^{*}$, $\widetilde{g}_{k-1}\circ\cdots\circ\widetilde{g}_{0}$
can be implemented by the ReLU neural network

$\overline{\mathcal{F}}\left(\sum_{i=0}^{k-1}(L_{i}+1),\left(d_{0},\underbrace{d_{1}p_{0},\ldots,d_{1}p_{0}}_{L_{0}\
\mbox{times}},\ldots,d_{k-1},\underbrace{d_{k}p_{k-1},\ldots,d_{k}p_{k-1}}_{L_{k-1}\
\mbox{times}},d_{k},d_{k}\right)\right).$

Note that $d_{i}\geq 1$ for all $0\leq i\leq k+1$ and $p_{i}\geq 1$ for $0\leq
i\leq k$. Denote

$\overline{p}=\max_{i=0,\ldots,k}d_{i+1}p_{i}.$

Finally, we can conclude that the function
$\widetilde{f}=\overline{g}_{k}\circ\widetilde{g}_{k-1}\cdots\circ\widetilde{g}_{0}$
can be implemented by the ReLU neural network
$\overline{\mathcal{F}}_{(\overline{L},(d_{0},\overline{p},\ldots,\overline{p},d_{k+1}))}$
with $\overline{L}=k+\sum_{i=0}^{k}L_{i}$.

Recall that $Q_{0}=1$, $Q_{i}=(2B)^{\alpha_{i}}$, for $i\in\\{1,\ldots,k-1\\}$
and $Q_{k}=2^{\alpha_{k}}B^{\alpha_{k}+1}$. Combining Lemma 7 with (6.5) and
(48) yields the following upper bound for the approximation error,

$\displaystyle\inf_{f\in\overline{\mathcal{F}}_{(\overline{L},(d_{0},\overline{p},\ldots,\overline{p},d_{k+1}))}}\|f^{\star}-f\|_{\infty}$
$\displaystyle\leq(2B)^{1+\sum_{i=1}^{k}\alpha_{i}}\left(\prod_{i=0}^{k}\sqrt{d_{i}}\right)\left[{\sum_{i=0}^{k}C_{\alpha_{i},t_{i},B}^{\prod_{l=i+1}^{k}(\alpha_{l}\wedge
1)}(\lceil
n^{t_{i}/2(t_{i}+2\alpha_{i}^{*})}\rceil)^{-2\alpha^{*}_{i}/t_{i}}}\right],$

where

$C_{\alpha_{i},t_{i},B}=19(2B)^{\alpha_{i}+1}(\lfloor\alpha_{i}\rfloor+1)^{2}t_{i}^{\lfloor\alpha_{i}\rfloor+(\alpha_{i}\vee
1)/2}.$

∎

###  6.6. Proof of Corollary 2

###### Proof.

Firstly, we establish an upper bound for the VC-dimension of the ReLU neural
network $\overline{\mathcal{F}}_{(\overline{L},\overline{p},K)}$. Using the
fact that for any $k$, ${\bf{d}}$, ${\bf{t}}$, ${\bm{\alpha}}$ and any $n\geq
1$, $\overline{L}\geq L_{0}\geq 65$, and $\overline{p}\geq p_{0}\geq 342$, we
can deduce, through the application of Proposition 1, that

$\displaystyle V(\overline{\mathcal{F}}_{(\overline{L},\overline{p},K)})$
$\displaystyle\leq
C_{d_{0}}\overline{p}^{2}\overline{L}^{2}\log_{2}\left(\overline{p}\overline{L}^{2}\right)$
(49) $\displaystyle\leq
C_{k,{\bf{d}},{\bf{t}},{\bm{\alpha}}}\left(\sum_{i=0}^{k}L_{i}\right)^{2}\log_{2}\left(\sum_{i=0}^{k}L_{i}\right),$

where $C_{k,{\bf{d}},{\bf{t}},{\bm{\alpha}}}>0$ is a numerical constant
depending only on $k,{\bf{d}},{\bf{t}}$ and ${\bm{\alpha}}$. Combining (7)
with the inequality (11), we obtain that for any $n\geq
V(\overline{\mathcal{F}}_{(\overline{L},\overline{p})})\geq
V(\overline{\mathcal{F}}_{(\overline{L},\overline{p},K)})$,

$\displaystyle{\mathbb{E}}\left[{\ell(Q_{f^{\star}},Q_{\widehat{f}})}\right]$
$\displaystyle\leq
C_{\epsilon,\sigma}\left[{\inf_{f\in{\mathcal{F}}_{(\overline{L},\overline{p},K)}}\|f^{\star}-f\|_{1,P_{W}}+\sqrt{\frac{V(\overline{\mathcal{F}}_{(\overline{L},\overline{p},K)})}{n}}}\right]$
(50) $\displaystyle\leq
C_{\epsilon,\sigma}\left[{\inf_{f\in\overline{\mathcal{F}}_{(\overline{L},\overline{p},K)}}\|f^{\star}-f\|_{1,P_{W}}+\sqrt{\frac{V(\overline{\mathcal{F}}_{(\overline{L},\overline{p},K)})}{n}}}\right],$

where the second inequality rises from the fact that
${\mathcal{F}}_{(\overline{L},\overline{p},K)}$ is dense in
$\overline{\mathcal{F}}_{(\overline{L},\overline{p},K)}$ with respect to the
sup-norm according to Lemma 3.

Finally, plugging the result provided in Proposition 3 and (49) into (50), we
can conclude that

$\displaystyle{\mathbb{E}}\left[{\ell(Q_{f^{\star}},Q_{\widehat{f}})}\right]$
$\displaystyle\leq
C_{\epsilon,\sigma,k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B}\left[{\left(\sum_{i=0}^{k}n^{-\frac{\alpha_{i}^{*}}{t_{i}+2\alpha_{i}^{*}}}\right)+\left(\sum_{i=0}^{k}L_{i}\right)\sqrt{\frac{\log_{2}\left(\sum_{i=0}^{k}L_{i}\right)}{n}}}\right]$
$\displaystyle\leq
C_{\epsilon,\sigma,k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B}\left[{\sum_{i=0}^{k}\left(n^{-\frac{\alpha_{i}^{*}}{t_{i}+2\alpha_{i}^{*}}}+\frac{L_{i}}{\sqrt{n}}\right)}\right]\sqrt{\log_{2}\left(\sum_{i=0}^{k}L_{i}\right)}$
$\displaystyle\leq
C_{\epsilon,\sigma,k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B}\left(\sum_{i=0}^{k}n^{-\frac{\alpha_{i}^{*}}{t_{i}+2\alpha_{i}^{*}}}\right)(\log
n)^{3/2}.$

∎

###  6.7. Proof of Theorem 2

To establish lower bounds, we initially prove the following variant of
Assouad’s lemma.

######  Lemma 8.

Let ${\mathcal{P}}$ be a family of probabilities on a measurable space
$({\mathscr{X}},{\mathcal{X}})$. If for some integer $D\geq 1$, there is a
subset of ${\mathcal{P}}$ of the form
$\left\\{P_{{\bm{\varepsilon}}},\;{\bm{\varepsilon}}\in\\{0,1\\}^{D}\right\\}$
satisfying

  1. (i)

there exists $\eta>0$ such that for all
${\bm{\varepsilon}},{\bm{\varepsilon}}^{\prime}\in\\{0,1\\}^{D}$,

$\|P_{{\bm{\varepsilon}}}-P_{{\bm{\varepsilon}}^{\prime}}\|_{TV}\geq\eta\delta({\bm{\varepsilon}},{\bm{\varepsilon}}^{\prime})\quad\text{with}\quad\delta({\bm{\varepsilon}},{\bm{\varepsilon}}^{\prime})=\sum_{j=1}^{D}1\hskip-2.6pt{\rm
l}_{{\varepsilon}_{j}\neq{\varepsilon}_{j}^{\prime}}$

  2. (ii)

there exists a constant $a\in\left[{0,1/2}\right]$ such that

$h^{2}\left({P_{{\bm{\varepsilon}}},P_{{\bm{\varepsilon}}^{\prime}}}\right)\leq\frac{a}{n}\quad\text{for
all ${\bm{\varepsilon}},{\bm{\varepsilon}}^{\prime}\in\\{0,1\\}^{D}$
satisfying $\delta({\bm{\varepsilon}},{\bm{\varepsilon}}^{\prime})=1$.}$

Then for all measurable mappings
$\widehat{P}:{\mathscr{X}}^{n}\to{\mathcal{P}}$,

(51)
$\sup_{P\in{\mathcal{P}}}{\mathbb{E}}_{{\mathbf{P}}}\left[{\|P-\widehat{P}({\bm{X}})\|_{TV}}\right]\geq\frac{\eta
D}{4}\max\left\\{{1-\sqrt{2a},\;\frac{1}{2}\left(1-\frac{a}{n}\right)^{2n}}\right\\},$

where ${\mathbb{E}}_{{\mathbf{P}}}$ denotes the expectation with respect to a
random variable ${\bm{X}}=(X_{1},\ldots,X_{n})$ with distribution
${\mathbf{P}}=P^{\otimes n}$.

###### Proof.

Let ${\bm{\overline{\varepsilon}}}$ minimize
${\bm{{\varepsilon}}}\mapsto\|P-P_{{\bm{{\varepsilon}}}}\|_{TV}$ over
$\\{0,1\\}^{D}$ for a given probability $P$ on
$({\mathscr{X}},{\mathcal{X}})$. Note that for all
${\bm{{\varepsilon}}}\in\\{0,1\\}^{D}$,

$\|P_{{\bm{{\varepsilon}}}}-P_{\overline{\bm{{\varepsilon}}}}\|_{TV}\leq\|P-P_{{\bm{{\varepsilon}}}}\|_{TV}+\|P-P_{\overline{\bm{{\varepsilon}}}}\|_{TV}\leq
2\|P-P_{{\bm{{\varepsilon}}}}\|_{TV}.$

Thus, using property (i), we have for all
${\bm{{\varepsilon}}}\in\\{0,1\\}^{D}$:

$\|P_{{\bm{{\varepsilon}}}}-P\|_{TV}\geq\frac{\eta}{2}\delta({\bm{{\varepsilon}}},\overline{\bm{{\varepsilon}}})=\sum_{i=1}^{D}\left[{{\varepsilon}_{i}\ell_{i}(P)+(1-{\varepsilon}_{i})\ell_{i}^{\prime}(P)}\right],$

where $\ell_{i}(P)=(\eta/2)1\hskip-2.6pt{\rm
l}_{\overline{\varepsilon}_{i}=0}$ and
$\ell_{i}^{\prime}(P)=(\eta/2)1\hskip-2.6pt{\rm
l}_{\overline{\varepsilon}_{i}=1}$, for $i\in\\{1,\ldots,D\\}$. Finally, the
conclusion follows by applying a version of Assouad’s lemma from Birgé, (1986)
with $\beta_{i}=a/n$, for all $i\in\\{1,\ldots,D\\}$ and $\alpha=\eta/2$. ∎

Now we prove Theorem 2. The roadmap is to first find a suitable collection of
probabilities ${\mathcal{P}}$ then apply Lemma 8 to derive the lower bound.

The construction idea is inspired by the proof of Theorem 3 of Schmidt-Hieber,
(2020). Denote $i^{*}\in\mathop{\rm
argmin}_{i=0,\ldots,k}\alpha^{*}_{i}/(2\alpha^{*}_{i}+t_{i})$. For simplicity,
we write $t^{*}=t_{i^{*}}$, $\alpha^{*}=\alpha_{i^{*}}$ and
$\alpha^{**}=\alpha^{*}_{i^{*}}$. We define $N_{n}=\lfloor\rho
n^{1/(2\alpha^{**}+t^{*})}\rfloor$, $h_{n}=1/N_{n}$ and
$\Lambda=\left\\{0,h_{n},\ldots,(N_{n}-1)h_{n}\right\\}$.

Following the construction outlined on page 93 of Tsybakov, (2009), we
consider the function

${\mathcal{K}}(x)=a\exp\left(-\frac{1}{1-(2x-1)^{2}}\right)1\hskip-2.6pt{\rm
l}_{|2x-1|\leq 1}$

with $a>0$. Provided that $a$ is sufficiently small, we have
${\mathcal{K}}\in{\mathcal{H}}^{\alpha^{*}}({\mathbb{R}},1)$ with support on
$\left[{0,1}\right]$. Moreover, for any $\beta\in{\mathbb{N}}$ satisfying
$\beta\leq\lfloor\alpha^{*}\rfloor$, the $\beta$-th derivative of
${\mathcal{K}}$ is zero at both $x=0$ and $x=1$, i.e.,
${\mathcal{K}}^{(\beta)}(0)={\mathcal{K}}^{(\beta)}(1)=0$. We define the
function $\psi_{\bf{u}}$ on $\left[{0,1}\right]^{t^{*}}$ as

$\psi_{\bf{u}}(w_{1},\ldots,w_{t^{*}})=h_{n}^{\alpha^{*}}\prod_{j=1}^{t^{*}}{\mathcal{K}}\left(\frac{w_{j}-u_{j}}{h_{n}}\right),$

where
${\bf{u}}=(u_{1},\ldots,u_{t^{*}})\in{\mathcal{U}}_{n}=\left\\{(u_{1},\ldots,u_{t^{*}}),\;u_{i}\in\Lambda\right\\}$.
Note that for any ${\bf{u}},{\bf{u}}^{\prime}\in{\mathcal{U}}_{n}$,
${\bf{u}}\not={\bf{u}}^{\prime}$, the supports of $\psi_{\bf{u}}$ and
$\psi_{{\bf{u}}^{\prime}}$ are disjoint. For any
${\bm{\beta}}=(\beta_{1},\ldots,\beta_{t^{*}})\in{\mathbb{N}}^{t^{*}}$
satisfying $\sum_{j=1}^{t^{*}}\beta_{j}\leq\lfloor\alpha^{*}\rfloor$, it holds
that $\|\partial^{\bm{\beta}}\psi_{\bf{u}}\|_{\infty}\leq 1$ due to the fact
that ${\mathcal{K}}\in{\mathcal{H}}^{\alpha^{*}}({\mathbb{R}},1)$. Set
${\mathcal{I}}_{\bf{u}}=\left[{u_{1},u_{1}+h_{n}}\right]\times\cdots\times\left[{u_{t^{*}},u_{t^{*}}+h_{n}}\right]$.
Moreover, for any ${\bm{\beta}}=(\beta_{1},\ldots,\beta_{t^{*}})$ with
$\sum_{j=1}^{t^{*}}\beta_{j}=\lfloor\alpha^{*}\rfloor$, with the fact that
${\mathcal{K}}\in{\mathcal{H}}^{\alpha^{*}}({\mathbb{R}},1)$ and triangle
inequality, we obtain that for any
${\bm{x}},{\bm{y}}\in{\mathcal{I}}_{\bf{u}}$,

$\frac{\big{|}\partial^{\bm{\beta}}\psi_{\bf{u}}({\bm{x}})-\partial^{\bm{\beta}}\psi_{\bf{u}}({\bm{y}})\big{|}}{\|{\bm{x}}-{\bm{y}}\|_{2}^{\alpha^{*}-\lfloor\alpha^{*}\rfloor}}\leq
t^{*}.$

Therefore, we have
$\psi_{\bf{u}}\in{\mathcal{H}}^{\alpha^{*}}({\mathcal{I}}_{\bf{u}},t^{*})$.
For any vector
${\bm{\varepsilon}}=({\varepsilon}_{{\bf{u}}})_{{\bf{u}}\in{\mathcal{U}}_{n}}\in\\{0,1\\}^{|{\mathcal{U}}_{n}|}$,
define the function $\phi_{{\bm{\varepsilon}}}$ on
$\left[{0,1}\right]^{t^{*}}$ as

$\phi_{{\bm{\varepsilon}}}(w_{1},\ldots,w_{t^{*}})=\sum_{{\bf{u}}\in{\mathcal{U}}_{n}}{\varepsilon}_{{\bf{u}}}\psi_{{\bf{u}}}(w_{1},\ldots,w_{t^{*}}).$

Given that ${\mathcal{K}}\in{\mathcal{H}}^{\alpha^{*}}({\mathbb{R}},1)$ and
${\mathcal{K}}^{(\beta)}(0)={\mathcal{K}}^{(\beta)}(1)=0$, for any
$\beta\leq\lfloor\alpha^{*}\rfloor$, it is not difficult to verify that
$\phi_{{\bm{\varepsilon}}}\in{\mathcal{H}}^{\alpha^{*}}(\left[{0,1}\right]^{t^{*}},2t^{*})$.

Let $d^{\prime}_{i}=\min\\{d_{0},\ldots,d_{i}\\}$, for all
$i\in\\{0,\ldots,k\\}$. For $0\leq i<i^{*}$, we denote
$f_{i}({\bm{w}})=(w_{1},\ldots,w_{d_{i+1}})^{\top}$, if
$d_{i+1}=d^{\prime}_{i+1}$; otherwise, we set
$f_{i}({\bm{w}})=(w_{1},\ldots,w_{d^{\prime}_{i}},0,\ldots,0)^{\top}$. We
denote
$f_{{\bm{\varepsilon}},i^{*}}({\bm{w}})=(\phi_{{\bm{\varepsilon}}}(w_{1},\ldots,w_{t^{*}}),0,\ldots,0)^{\top}$,
$f_{i}({\bm{w}})=(w_{1}^{\alpha_{i}\wedge 1},0,\ldots,0)^{\top}$, for
$i^{*}<i\leq k-1$ and $f_{k}({\bm{w}})=w_{1}^{\alpha_{k}\wedge 1}$. Let
${\mathcal{A}}=\prod_{l=i^{*}+1}^{k}(\alpha_{l}\wedge 1)$. Since
$t_{j}\leq\min(d_{0},\ldots,d_{j-1})$, we can set

$\displaystyle f_{{\bm{\varepsilon}}}({\bm{w}})$
$\displaystyle=f_{k}\circ\cdots\circ f_{i^{*}+1}\circ
f_{{\bm{\varepsilon}},i^{*}}\circ f_{i^{*}-1}\circ\cdots\circ f_{0}({\bm{w}})$
$\displaystyle=\sum_{{\bf{u}}\in{\mathcal{U}}_{n}}{\varepsilon}_{{\bf{u}}}\left[{\psi_{\bf{u}}(w_{1},\ldots,w_{t^{*}})}\right]^{{\mathcal{A}}}.$

Consequently, we can observe that the resulting function
$f_{{\bm{\varepsilon}}}$ belongs to the class
${\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)$ when $B$ is sufficiently
large.

Since $W$ is uniformly distributed on $\left[{0,1}\right]^{d_{0}}$, we can
compute

(52)
$\|f_{{\bm{\varepsilon}}}-f_{{\bm{\varepsilon}}^{\prime}}\|_{2}^{2}=\delta({\bm{\varepsilon}},{\bm{\varepsilon}}^{\prime})h_{n}^{2\alpha^{**}+t^{*}}\|{\mathcal{K}}^{{\mathcal{A}}}\|_{2}^{2t^{*}}$

and

(53)
$\|f_{{\bm{\varepsilon}}}-f_{{\bm{\varepsilon}}^{\prime}}\|_{1}=\delta({\bm{\varepsilon}},{\bm{\varepsilon}}^{\prime})h_{n}^{\alpha^{**}+t^{*}}\|{\mathcal{K}}^{{\mathcal{A}}}\|_{1}^{t^{*}},$

where $\delta(\cdot,\cdot)$ denotes the Hamming distance. For any
$P_{f_{{\bm{\varepsilon}}}}=Q_{f_{{\bm{\varepsilon}}}}\cdot P_{W}$ and
$P_{f_{{\bm{\varepsilon}}^{\prime}}}=Q_{f_{{\bm{\varepsilon}}^{\prime}}}\cdot
P_{W}$, where $P_{W}$ is the uniform distribution on
$\left[{0,1}\right]^{d_{0}}$, we can derive that

$\displaystyle
h^{2}(P_{f_{{\bm{\varepsilon}}}},P_{f_{{\bm{\varepsilon}}^{\prime}}})$
$\displaystyle=\int_{{\mathscr{W}}}\left(1-\exp\left[{-\frac{|f_{{\bm{\varepsilon}}}(w)-f_{{\bm{\varepsilon}}^{\prime}}(w)|^{2}}{8\sigma^{2}}}\right]\right)dP_{W}(w)$
$\displaystyle\leq\int_{{\mathscr{W}}}\frac{|f_{{\bm{\varepsilon}}}(w)-f_{{\bm{\varepsilon}}^{\prime}}(w)|^{2}}{8\sigma^{2}}dP_{W}(w)$
(54)
$\displaystyle=\frac{\|f_{{\bm{\varepsilon}}}-f_{{\bm{\varepsilon}}^{\prime}}\|^{2}_{2}}{8\sigma^{2}}.$

According to Lemma 2, we can deduce that for $W$ uniformly distributed on
$\left[{0,1}\right]^{d_{0}}$,

(55)
$\ell(Q_{f_{{\bm{\varepsilon}}}},Q_{f_{{\bm{\varepsilon}}^{\prime}}})=\|P_{f_{{\bm{\varepsilon}}}}-P_{f_{{\bm{\varepsilon}}^{\prime}}}\|_{TV}\geq\frac{0.78}{\sqrt{2\pi}\sigma}\|f_{{\bm{\varepsilon}}}-f_{{\bm{\varepsilon}}^{\prime}}\|_{1},$

provided $\rho\geq
1+\left[{\|{\mathcal{K}}^{{\mathcal{A}}}\|_{1}^{t^{*}}/(\sqrt{2\pi}\sigma)}\right]^{1/\alpha^{**}}$
such that
$h_{n}^{\alpha^{**}}\leq\sqrt{2\pi}\sigma/\|{\mathcal{K}}^{{\mathcal{A}}}\|_{1}^{t^{*}}$.
Putting (52), (53), (54) and (55) together, we observe that the family of
probabilities
${\mathcal{P}}=\\{P_{{\bm{\gamma}}_{{\bm{\varepsilon}}}},\;{\bm{\varepsilon}}\in\\{0,1\\}^{|{\mathcal{U}}_{n}|}\\}$
satisfies the assumptions of Lemma 8 with $D=N_{n}^{t^{*}}$,

$\eta=\frac{0.78}{\sqrt{2\pi}\sigma}h_{n}^{\alpha^{**}+t^{*}}\|{\mathcal{K}}^{{\mathcal{A}}}\|_{1}^{t^{*}}\quad\text{and}\quad
a=\frac{1}{8\sigma^{2}}nh_{n}^{2\alpha^{**}+t^{*}}\|{\mathcal{K}}^{{\mathcal{A}}}\|_{2}^{2t^{*}}.$

Finally, taking the constant

$\rho\geq\left[{1+\left(\frac{\|{\mathcal{K}}^{{\mathcal{A}}}\|_{1}^{t^{*}}}{\sqrt{2\pi}\sigma}\right)^{\frac{1}{\alpha^{**}}}}\right]\vee\left[{1+\left(\frac{\|{\mathcal{K}}^{{\mathcal{A}}}\|_{2}^{2t^{*}}}{\sigma^{2}}\right)^{\frac{1}{2\alpha^{**}+t^{*}}}}\right]$

such that
$h_{n}^{\alpha^{**}}\leq(n\|{\mathcal{K}}^{{\mathcal{A}}}\|_{2}^{2t^{*}}/\sigma^{2})^{-\frac{\alpha^{**}}{2\alpha^{**}+t^{*}}}\wedge\left(\sqrt{2\pi}\sigma/\|{\mathcal{K}}^{{\mathcal{A}}}\|_{1}^{t^{*}}\right)$,
we derive by Lemma 8 that there exists some constant $c>0$ such that

$\inf_{\widehat{f}}\sup_{f^{\star}\in{\mathcal{F}}(k,{\bf{d}},{\bf{t}},{\bm{\alpha}},B)}{\mathbb{E}}\left[{\ell(Q_{f^{\star}},Q_{\widehat{f}})}\right]\geq
cn^{-\frac{\alpha^{**}}{2\alpha^{**}+t^{*}}}.$

## References

  * Baraud, (2016) Baraud, Y. (2016).  Bounding the expectation of the supremum of an empirical process over a (weak) VC-major class.  Electron. J. Statist., 10, 1709–1728.
  * Baraud, (2021) Baraud, Y. (2021).  Tests and estimation strategies associated to some loss functions.  Probab. Theory Related Fields, 180, 799–846.
  * Baraud and Birgé, (2018) Baraud, Y. and Birgé, L. (2018).  Rho-estimators revisited: General theory and applications.  Ann. Statist., 46, 3767–3804.
  * Baraud and Birgé, (2014) Baraud, Y. and Birgé, L. (2014).  Estimating composite functions by model selection.  Ann. Inst. H. Poincaré Probab. Statist., 50, 285–314.
  * Baraud et al., (2017) Baraud, Y., Birgé, L. and Sart, M. (2017).  A new method for estimation and model selection: $\rho$-estimation.  Invent. Math., 207, 425–517.
  * Baraud and Chen, (2020) Baraud, Y. and Chen, J. (2020).  Robust estimation of a regression function in exponential families.  arXiv:2011.01657.
  * Baraud et al., (2022) Baraud, Y., Halconruy, H. and Maillard, G. (2022).  Robust density estimation with the ${\mathbb{L}}_{1}$-loss. Applications to the estimation of a density on the line satisfying a shape constraint.  arXiv:2205.10524.
  * Bartlett et al., (2019) Bartlett, P. L., Harvey, N., Liaw, C. and Mehrabian, A. (2019).  Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks.  J. Mach. Learn. Res., 20, 1–17.
  * Barron, (2019) Barron, J. T. (2019).  A general and adaptive robust loss function. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 4331–4339.
  * Bassett and Koenker, (1978) Bassett, G. and Koenker, M. (1992).  Asymptotic theory of least absolute error regression.  J. Amer. Statist. Assoc., 73, 618–622.
  * Bauer and Kohler, (2019) Bauer, B. and Kohler, M. (2019).  On deep learning as a remedy for the curse of dimensionality in nonparametric regression.  Ann. Statist., 47, 2261–2285.
  * Beaton and Tukey, (1974) Beaton, A. E. and Tukey, J. W. (1974).  The fitting of power series, meaning polynomials, illustrated on band-spectroscopic data.  Technometrics, 16, 147–185.
  * Birgé, (1986) Birgé, L. (1986).  On estimating a density using Hellinger distance and some other strange facts.  Probab. Theory Relat. Fields, 71, 271–291.
  * Chen, (2022) Chen, J. (2022).  Estimating a regression function in exponential families by model selection.  arXiv:2203.06656.
  * Chen et al., (2019) Chen, M., Jiang, H., Liao, W. and Zhao, T. (2019).  Efficient approximation of deep ReLU networks for functions on low dimensional manifolds. In 32th Advances in Neural Information Processing Systems, NeurIPS.
  * Chen et al., (2022) Chen, M., Jiang, H., Liao, W. and Zhao, T. (2022).  Nonparametric regression on low-dimensional manifolds using deep ReLU networks: function approximation and statistical recovery.  Inf. Inference, 11, 1203–1253.
  * Donoho and Johnstone, (1998) Donoho, D. L. and Johnstone, I. M. (1998).  Minimax estimation via wavelet shrinkage.  Ann. Statist., 26, 879–921.
  * Donoho et al., (1995) Donoho, D. L., Johnstone, I. M., Kerkyacharian, G. and Picard, D. (1995).  Wavelet shrinkage: Asymptopia?  J. Roy. Statist. Soc., Ser. B, 57, 301–369.
  * Fan, (1992) Fan, J. (1992).  Design-adaptive nonparametric regression.  J. Amer. Statist. Assoc., 87, 998–1004.
  * Fan, (1993) Fan, J. (1993).  Local linear regression smoothers and their minimax efficiencies.  Ann. Statist., 21, 196–216.
  * Friedman, (1991) Friedman, J. (1991).  Multivariate adaptive regression splines.  Ann. Statist., 19, 1–67.
  * Györfi et al., (2002) Györfi, L., Kohler, M., Krzyzak, A. and Walk, H. (2002).  A Distribution-Free Theory of Nonparametric Regression.  Springer Series in Statistics. Springer-Verlag, New York.
  * Horowitz and Mammen, (2007) Horowitz, J. L. and Mammen, E. (2007).  Rate-optimal estimation for a general class of nonparametric regression models with unknown link functions.  Ann. Statist., 35, 2589–2619.
  * Huber, (1973) Huber, P. J. (1973).  Robust regression: asymptotics, conjectures and Monte Carlo.  Ann. Statist., 1, 799–821.
  * Jiao et al., (2021) Jiao, Y., Shen, G., Lin, Y. and Huang, J. (2021).  Robust nonparametric regression with deep neural networks.  arXiv:2107.10343.
  * Jiao et al., (2023) Jiao, Y., Shen, G., Lin, Y. and Huang, J. (2023).  Deep nonparametric regression on approximate manifolds: non-asymptotic error bounds with polynomial prefactors.  Ann. Statist., 51, 691–716.
  * Kohler and Langer, (2021) Kohler, M. and Langer, S. (2021).  On the rate of convergence of fully connected deep neural network regression estimates.  Ann. Statist., 49, 2231–2249.
  * Lederer, (2020) Lederer, J. (2020).  Risk bounds for robust deep learning.  arXiv:2009.06202.
  * Nadaraya, (1964) Nadaraya, E. A. (1964)  On estimating regression.  Theory Probab. its Appl., 9, 141–142.
  * Nakada and Imaizumi, (2020) Nakada, R. and Imaizumi, M. (2020)  Adaptive approximation and generalization of deep neural network with intrinsic dimensionality.  J. Mach. Learn. Res., 21, 1–38.
  * Padilla et al., (2022) Padilla, O. H. M., Tansey, W. and Chen, Y. (2022)  Quantile regression with ReLU networks: Estimators and minimax rates.  J. Mach. Learn. Res., 23, 1–42.
  * Schmidt-Hieber, (2019) Schmidt-Hieber, J. (2019).  Deep ReLU network approximation of functions on a manifold.  arXiv:1908.00695.
  * Schmidt-Hieber, (2020) Schmidt-Hieber, J. (2020).  Nonparametric regression using deep neural networks with ReLU activation function.  Ann. Statist., 48, 1875–1897.
  * Stone, (1982) Stone, C. J. (1982).  Optimal global rates of convergence for nonparametric regression.  Ann. Statist., 10, 1040–1053.
  * Stone, (1985) Stone, C. J. (1985).  Additive regression and other nonparametric models.  Ann. Statist., 13, 689–705.
  * Suzuki, (2019) Suzuki, T. (2019).  Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In 7th International Conference on Learning Representations, ICLR.
  * Suzuki and Nitanda, (2021) Suzuki, T. and Nitanda, A. (2021).  Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. In 34th Advances in Neural Information Processing Systems, NeurIPS.
  * Tsybakov, (2009) Tsybakov, A. B. (2009).  Introduction to Nonparametric Estimation.  Springer Series in Statistics. Springer-Verlag, New York.
  * van der Vaart and Wellner, (1996) van der Vaart, A. W. and Wellner, J. A. (1996).  Weak Convergence and Empirical Processes. With Applications to Statistics.  Springer Series in Statistics. Springer-Verlag, New York.
  * van der Vaart and Wellner, (2009) van der Vaart, A. and Wellner, J. A. (2009).  A note on bounds for VC dimensions.  In High Dimensional Probability V: the Luminy volume, volume 5 of Inst. Math. Stat. Collect., pages 103–107. Inst. Math. Statist., Beachwood, OH.
  * Wahba, (1990) Wahba, G. (1990).  Spline Models for Observational Data.  Society for Industrial and Applied Mathematics.
  * Watson, (1964) Watson, G. S. (1964).  Smooth regression analysis.  Sankhyā: Indian J. Stat., Ser. A, 26, 359–372.