Robust nonparametric regression based on deep ReLU neural networks
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\"older 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\"older 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.
Juntong Chen
# Robust nonparametric regression based on deep relu neural networks

###### 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\)-Holder 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 Holder 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 N\({}^{\text{o}}\) 811017.
and \(f^{\star}:\mathscr{W}\to\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 Gyorfi et al. (2002) and Tsybakov (2009). Particularly, when \(f^{\star}:[0,1]^{d}\to\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 Birge (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 feed-forward 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 Holder 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. 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. 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. 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 Holder 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. 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 Holder 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 Holder 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 Holder 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 \(\boldsymbol{\mathscr{Q}}_{\mathscr{W}}=\mathscr{Q}_{\mathscr{W}}^{n}\). As a direct result, we obtain the \(n\)-tuple \(\mathbf{Q}^{\star}=(Q_{1}^{\star},\ldots,Q_{n}^{\star})\in\boldsymbol{ \mathscr{Q}}_{\mathscr{W}}\). We equip the space \(\boldsymbol{\mathscr{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_{1}^{\prime},\ldots,Q_{n}^{\prime})\) in \(\boldsymbol{\mathscr{Q}}_{\mathscr{W}}\),

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

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

Building on the \(n\) observations \(\boldsymbol{X}=(X_{1},\ldots,X_{n})\), we will introduce an estimation approach in the later section to develop an estimator \(\widehat{f}(\boldsymbol{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_{1}^{\star},\ldots,Q_{n}^{\star})\) 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:

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

In the case where \(W_{i}\) are i.i.d. with the common distribution \(P_{W}\) and \(Q_{i}^{\star}=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

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

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\boldsymbol{\mathscr{Q}}_{\mathscr{W}}\) and a set \(\mathbf{A}\subset\boldsymbol{\mathscr{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[1,+\infty]\), 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}=\begin{cases}\left(\int_{E}|f|^{k}d\mu\right)^{1/k},&\text{for $k \in[1,+\infty)$},\\ \inf\{K>0,\;|f|\leq K\;\mu-\text{a.e.}\},&\text{for $k=\infty$}.\end{cases}\]

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[1,+\infty]\) 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{\mathscr{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.

### 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)=\mathbbm{1}_{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_

\[\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}}). \tag{4}\]

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 \(\mathbf{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}(\mathbf{X},f_{1},f_{2})=\sum_{i=1}^{n}t_{(f_{1},f_{2})}(W_{i},Y_{i})\]

and set

\[\mathbf{T}_{l}(\mathbf{X},f_{1})=\sup_{f_{2}\in\mathcal{F}}\mathbf{T}_{l}(\mathbf{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}(\mathbf{X})\) is an \(\epsilon\)-minimizer over \(\mathcal{F}\) of the map \(f_{1}\mapsto\mathbf{T}_{l}(\mathbf{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}(\mathbf{X})\) of the random (and non-void) set

\[\mathscr{E}(\mathbf{X},\epsilon)=\left\{f\in\mathcal{F},\ \mathbf{T}_{l}(\mathbf{X},f) \leq\inf_{f^{\prime}\in\mathcal{F}}\mathbf{T}_{l}(\mathbf{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}(\mathbf{X},f)=\inf_{f^{\prime}\in\mathcal{F}}\mathbf{T}_{l}(\mathbf{X}, f^{\prime})\), it is advisable to prioritize this \(f\) as the estimator \(\widehat{f}\).

Furthermore, considering that \(\mathbf{T}_{l}(\mathbf{X},f)\geq\mathbf{T}_{l}(\mathbf{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}(\mathbf{X},\widehat{f})\leq\epsilon\) qualifies as an \(\ell\)-type estimator.
### 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}(\mathbf{X})\).

**Theorem 1**.: _Under Assumption 1, whatever the conditional distributions \(\mathbf{Q}^{\star}=(Q_{1}^{\star},\ldots,Q_{n}^{\star})\) 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}\),_

\[\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}. \tag{5}\]

_In particular, with the triangle inequality,_

\[\ell(\mathbf{Q}^{\star},\mathbf{Q}_{\widehat{f}})\leq 3\ell(\mathbf{Q}^{ \star},\boldsymbol{\mathscr{Q}})+291.2\sqrt{\frac{V}{n}}+14573.4\frac{V}{n}+ \sqrt{\frac{8(\xi+\log 2)}{n}}+\frac{\epsilon}{n}, \tag{6}\]
_where \(\boldsymbol{\mathscr{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}})\)_

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

_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{\boldsymbol{\mathscr{Q}}}=\{\mathbf{Q}_{f},\ f\in\overline{ \mathcal{F}}\}\). It is clear that if \(\boldsymbol{\mathscr{Q}}\) is dense in \(\overline{\boldsymbol{\mathscr{Q}}}\) with respect to the (pseudo) distance \(\ell\), both (6) and (7) also remain valid when replacing \(\boldsymbol{\mathscr{Q}}\) with \(\overline{\boldsymbol{\mathscr{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 Birge (2018). For the sake of simplicity in our explanation, let us temporarily assume in this section that \(\boldsymbol{\mathscr{Q}}\) is dense in \(\overline{\boldsymbol{\mathscr{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{\boldsymbol{\mathscr{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_{i}^{\star}=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{\boldsymbol{\mathscr{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

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

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 \([0,1]\) 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

\[\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\|P_{i}^{\star}-P_{i,\widehat {f}}\|_{TV}\right] \leq C_{\epsilon}\left[\frac{1}{n}\sum_{i=1}^{n}\|P_{i}^{\star}-P_ {i,\overline{f}}\|_{TV}+\sqrt{\frac{V}{n}}\right] \tag{9}\] \[\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}=\leavevmode\hbox{\small 1\kern-3.8pt\normalsize 1}_{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}\).

### 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}(\mathbf{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_

\[\|Q_{f(w)}-Q_{f^{\prime}(w)}\|_{TV}=1-2\Phi\left(-\frac{|f^{\prime}(w)-f(w)|}{ 2\sigma}\right), \tag{10}\]
_where the notation \(\Phi\) stands for the cumulative distribution function of the standard normal distribution. Consequently,_

\[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\}\,. \tag{11}\]

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}\),

\[\|Q_{f(w)}-Q_{f^{\prime}(w)}\|_{TV} =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)\] \[=\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) \tag{12}\] \[=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

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

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

\[\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], \tag{14}\]

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}(\mathbf{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.
### 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 Birge (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_{i}^{\star}=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}(\mathbf{X})\) satisfies

\[\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], \tag{15}\]

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}(\mathbf{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

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

we can deduce, using Holder'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

\[\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]. \tag{16}\]

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\text{for some small $\beta\in(0,1)$},\]

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

\[\|P^{\star}-P_{f^{\star}}\|_{TV}=\beta\|P_{f^{\star}}-R\|_{TV}, \tag{17}\]

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

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

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\}\).

### 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 \(\mathbf{x}=(x_{1},\ldots,x_{p})^{\top}\in\mathbb{R}^{p}\), where \(p\in\mathbb{N}^{*}\), the notation \(\sigma(\mathbf{x})\) represents the activation function applied component-wise, defined as follows:

\[\sigma(\mathbf{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 \(\mathbf{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,\mathbf{p})}\) as a collection of functions of the form:

\[f:\mathbb{R}^{d}\to\mathbb{R},\quad\mathbf{w}\mapsto f(\mathbf{w})=M_{L}\circ\sigma \circ M_{L-1}\circ\cdots\circ\sigma\circ M_{0}(\mathbf{w}),\]

where

\[M_{l}(\mathbf{y})=A_{l}(\mathbf{y})+b_{l},\quad\text{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,\mathbf{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,\mathbf{p},K)}\subset\overline{\mathcal{F}}_{(L,\mathbf{ p})}\), denoting the set of all functions with parameters ranging within the interval \([-K,K]\). Furthermore, we use the notation \(\mathcal{F}_{(L,\mathbf{p})}\) (or \(\mathcal{F}_{(L,\mathbf{p},K)}\)) for the multi-layer perceptron, which shares the same architecture as \(\overline{\mathcal{F}}_{(L,\mathbf{p})}\) (or \(\overline{\mathcal{F}}_{(L,\mathbf{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,\mathbf{p})}\) (or \(\mathcal{F}_{(L,\mathbf{p},K)}\) respectively) for \(\mathbf{p}=(d,p,\ldots,p,1)\).

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

**Lemma 3**.: _For any \(L\in\mathbb{N}^{*}\), \(\mathbf{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,\mathbf{p},K)}\) is dense in \(\overline{\mathcal{F}}_{(L,\mathbf{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,\boldsymbol{p},K)}\) does not compromise approximation power compared to \(\overline{\mathcal{F}}_{(L,\boldsymbol{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_

\[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], \tag{19}\]

_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.

### Approximating functions in Holder 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 Holder class.

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

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

where for any \(\boldsymbol{\beta}=(\beta_{1},\ldots,\beta_{t})^{\top}\in\mathbb{N}^{t}\), \(\partial^{\boldsymbol{\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}(8 N)\rceil\]

_and a depth of_

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

_such that_

\[\left|f(\boldsymbol{w})-\overline{f}(\boldsymbol{w})\right|\leq 19B(\lfloor \alpha\rfloor+1)^{2}d^{\lfloor\alpha\rfloor+\frac{\alpha\lor 1}{2}}(NM)^{-\frac{2 \alpha}{d}},\]

_for all \(\boldsymbol{w}\in[0,1]^{d}\)._

In fact, several approximation results have been established regarding the Holder 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}(\boldsymbol{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)})\),_

\[\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}(2 N)\log_{2}(2M)\right)^{3/2}\right], \tag{20}\]

_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:_

\[\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}. \tag{21}\]

_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\)-Holder 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}^{*}\), \(\mathbf{d}=(d_{0},\ldots,d_{k})\in(\mathbb{N}^{*})^{k+1}\), \(\mathbf{t}=(t_{0},\ldots,t_{k})\in(\mathbb{N}^{*})^{k+1}\), \(\boldsymbol{\alpha}=(\alpha_{0},\ldots,\alpha_{k})\in(\mathbb{R}_{+}^{*})^{k+1}\) and a finite constant \(B\geq 0\), we denote \(\mathcal{F}(k,\mathbf{d},\mathbf{t},\boldsymbol{\alpha},B)\) the class of functions as,

\[\mathcal{F}(k,\mathbf{d},\mathbf{t},\boldsymbol{\alpha},B)= \left\{f_{k}\circ\cdots\circ f_{0},\;f_{i}=(f_{ij})_{j}:[a_{i},b_{i}]^{d_{i} }\to[a_{i+1},b_{i+1}]^{d_{i+1}}\,,\right. \tag{22}\] \[\left.f_{ij}\in\mathcal{H}^{\alpha_{i}}(\left[a_{i},b_{i}\right]^{ t_{i}},B)\text{ 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
\(\mathcal{F}(k,\mathbf{d},\mathbf{t},\boldsymbol{\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\), \(\mathbf{d}\), \(\mathbf{t}\) and \(\boldsymbol{\alpha}\) are considered to be known. We will then proceed to construct suitable networks for approximating the class \(\mathcal{F}(k,\mathbf{d},\mathbf{t},\boldsymbol{\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\text{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,\mathbf{d},\mathbf{t},\boldsymbol{\alpha},B)\).

**Proposition 3**.: _Assuming that \(f\in\mathcal{F}(k,\mathbf{d},\mathbf{t},\boldsymbol{\alpha},B)\) with \(\mathcal{F}(k,\mathbf{d},\mathbf{t},\boldsymbol{\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_

\[\|f-\overline{f}\|_{\infty}\] \[\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}\lor 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,\mathbf{d},\mathbf{t},\boldsymbol{\alpha},B)\) with \(\mathcal{F}(k,\mathbf{d},\mathbf{t},\boldsymbol{\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}(\mathbf{X})\) implemented by a ReLU neural network \(\mathcal{F}_{(\overline{L},\overline{p},K)}\) with_

\[\overline{L}=k+\sum_{i=0}^{k}L_{i},\qquad\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})})\),_

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

_where \(C_{\epsilon,\sigma,k,\mathbf{d},\mathbf{t},\mathbf{\alpha},B}\) is a numerical constant depending on \(\epsilon,\sigma,k,\mathbf{d},\mathbf{t},\mathbf{\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}^{\star}/(2\alpha_{i}^{\star}+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,\mathbf{d},\mathbf{t},\mathbf{\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,\mathbf{d},\mathbf{t},\mathbf{\alpha},B)\), a bias term \(\inf_{f\in\mathcal{F}(k,\mathbf{d},\mathbf{t},\mathbf{\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 \([0,1]^{d_{0}}\).

**Theorem 2**.: _Let \(P_{W}\) be the uniform distribution on \([0,1]^{d_{0}}\). For any \(k\in\mathbb{N}^{*}\), \(\mathbf{d}\in(\mathbb{N}^{*})^{k+1}\), \(\mathbf{t}\in(\mathbb{N}^{*})^{k+1}\) such that \(t_{j}\leq\min(d_{0},\ldots,d_{j-1})\) for all \(j\), any \(\mathbf{\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,\mathbf{d},\mathbf{t},\mathbf{ \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

### 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

\[\mathbb{E}_{P^{\star}}\left[t_{(f_{1},f_{2})}(W,Y)\right]\] \[= \int_{\mathscr{W}}\left[Q_{(w)}^{\star}\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)\] \[\leq \int_{\mathscr{W}}\|Q_{(w)}^{\star}-Q_{f_{1}(w)}\|_{TV}dP_{W}(w)\] \[= \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

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

which yields the first inequality in (4). 

### 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 \(\{\widetilde{q}_{f},\ f\in\mathcal{F}\}\) 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, \(\{\widetilde{q}_{f},\ f\in\mathcal{F}\}\) 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_{1}^{\star},\ldots,Q_{n}^{\star})\) 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}\),_

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

_where_

\[\boldsymbol{\vartheta}(\overline{f})= \mathbb{E}\left[\sup_{f^{\prime}\in\mathcal{F}}\left[\mathbf{T}_{ l}(\boldsymbol{X},\overline{f},f^{\prime})-\mathbb{E}\left[\mathbf{T}_{l}( \boldsymbol{X},\overline{f},f^{\prime})\right]\right]\right]\] \[\vee\mathbb{E}\left[\sup_{f^{\prime}\in\mathcal{F}}\left[ \mathbb{E}\left[\mathbf{T}_{l}(\boldsymbol{X},f^{\prime},\overline{f})\right] -\mathbf{T}_{l}(\boldsymbol{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}_{+}(\mathbf{X},f_{1}) =\sup_{f_{2}\in\mathcal{F}}\left[\mathbf{T}_{l}(\mathbf{X},f_{1},f_{2} )-\mathbb{E}\left[\mathbf{T}_{l}(\mathbf{X},f_{1},f_{2})\right]\right]\] \[\mathbf{Z}_{-}(\mathbf{X},f_{1}) =\sup_{f_{2}\in\mathcal{F}}\left[\mathbb{E}\left[\mathbf{T}_{l}( \mathbf{X},f_{2},f_{1})\right]-\mathbf{T}_{l}(\mathbf{X},f_{2},f_{1})\right]\]

and set

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

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

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

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

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

Moreover, we can compute that

\[\mathbf{T}_{l}(\mathbf{X},\overline{f}) =\sup_{f\in\mathcal{F}}\mathbf{T}_{l}(\mathbf{X},\overline{f},f) \tag{27}\] \[\leq\sup_{f\in\mathcal{F}}\left[\mathbf{T}_{l}(\mathbf{X},\overline{f },f)-\mathbb{E}\left[\mathbf{T}_{l}(\mathbf{X},\overline{f},f)\right]\right]+\sup_ {f\in\mathcal{F}}\mathbb{E}\left[\mathbf{T}_{l}(\mathbf{X},\overline{f},f)\right]\] \[\leq\mathbf{Z}(\mathbf{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}\),

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

In what follows, we study the term \(\mathbf{Z}(\mathbf{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 \(\mathbf{x}=(x_{1},\ldots,x_{n})\in\mathscr{X}^{n}\) and \(\mathbf{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}_{+}(\mathbf{x},\overline{f})-\mathbf{Z}_{+}(\mathbf{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}\),

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

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

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

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

\[\mathbf{Z}(\mathbf{X},\overline{f})=\mathbf{Z}_{+}(\mathbf{X},\overline{f})\lor \mathbf{Z}_{-}(\mathbf{X},\overline{f})\leq\mathbf{\vartheta}(\overline{f})+\sqrt{2n (\xi+\log 2)}. \tag{31}\]

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

\[\ell(\mathbf{Q}_{\overline{f}},\mathbf{Q}_{\widehat{f}})\leq 2\ell(\mathbf{Q }^{*},\mathbf{Q}_{\overline{f}})+\frac{2\mathbf{\vartheta}(\overline{f})}{n}+ \sqrt{\frac{8(\xi+\log 2)}{n}}+\frac{\epsilon}{n}. \tag{32}\]

**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}\mathds{1}_{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}\mathds{1}_ {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)\),

\[Q_{f_{1}(w)}(q_{f_{2}(w)}>q_{f_{1}(w)}) =\int_{-\infty}^{[f_{1}(w)+f_{2}(w)]/2}q_{f_{1}(w)}(y)dy\] \[=\int_{-\infty}^{[f_{2}(w)-f_{1}(w)]/2\sigma}\frac{1}{\sqrt{2\pi }}e^{-\frac{t^{2}}{2}}dt\] \[=\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)\),

\[Q_{f_{1}(w)}(q_{f_{2}(w)}>q_{f_{1}(w)}) =\int_{[f_{1}(w)+f_{2}(w)]/2}^{+\infty}q_{f_{1}(w)}(y)dy\] \[=\int_{[f_{2}(w)-f_{1}(w)]/2\sigma}^{+\infty}\frac{1}{\sqrt{2 \pi}}e^{-\frac{t^{2}}{2}}dt\] \[=1-\Phi\left(\frac{f_{2}(w)-f_{1}(w)}{2\sigma}\right)\] \[=\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(\mathds{1}_{C }(X_{i})-\mathbb{P}(X_{i}\in C)\right)\Big{|}\right]\leq 10(\sigma\lor a) \sqrt{nV\left[5+\log\left(\frac{1}{\sigma\lor 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_{f\in\mathcal{F}}\left|\sum_{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 \(\boldsymbol{\vartheta}(\overline{f})\). Let us express \(\boldsymbol{\vartheta}(\overline{f})\) as \(\boldsymbol{\vartheta}(\overline{f})=\boldsymbol{\vartheta}_{1}(\overline{f}) \vee\boldsymbol{\vartheta}_{2}(\overline{f})\), where

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

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

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

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

\[g_{(f_{1},f_{2})}(w,y)=\mbox{1l}_{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}\mbox{1l}_{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}\),

\[t_{(f_{1},f_{2})}(w,y) =g_{(f_{1},f_{2})}(w,y)-\left[h_{(f_{1},f_{2})}(w)-k_{(f_{1},f_{2} )}(w)\right] \tag{33}\] \[=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

\[\boldsymbol{\vartheta}_{1}(\overline{f}) =\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]\] \[\leq\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]\] \[\quad+\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]\] \[\quad+\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

\[\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}. \tag{34}\]

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

\[\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}. \tag{35}\]
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

\[\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. \tag{36}\]

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

\[\boldsymbol{\vartheta}_{1}(\overline{f})\leq 145.6\sqrt{nV}+7286.7V. \tag{37}\]

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

\[\boldsymbol{\vartheta}_{2}(\overline{f})\leq 145.6\sqrt{nV}+7286.7V. \tag{38}\]

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

\[\boldsymbol{\vartheta}(\overline{f})=\boldsymbol{\vartheta}_{1}(\overline{f} )\vee\boldsymbol{\vartheta}_{2}(\overline{f})\leq 145.6\sqrt{nV}+7286.7V. \tag{39}\]

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}\),

\[\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}, \tag{40}\]

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},\boldsymbol{\mathscr{Q}})+291.2\sqrt{\frac{V}{n}}+14573.4\frac{V}{n}+ \sqrt{\frac{8(\xi+\log 2)}{n}}+\frac{\epsilon}{n}.\]
### 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,\boldsymbol{p},K)}\), there exists a sequence of functions \(f_{i}\in\mathcal{F}_{(L,\boldsymbol{p},K)}\), \(i\in\mathbb{N}^{*}\) such that

\[\lim_{i\to+\infty}\|f-f_{i}\|_{\infty}=0.\]

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

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

where

\[M_{l}(\boldsymbol{y})=A_{l}(\boldsymbol{y})+b_{l},\quad\text{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}\to\mathbb{R}^{p_{l}}\),

\[f_{l}^{+}(\boldsymbol{w})=\sigma\circ M_{l-1}\circ\cdots\circ\sigma\circ M_{0 }(\boldsymbol{w})\]

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

\[f_{l}^{-}(\boldsymbol{x})=M_{L}\circ\sigma\circ\cdots\circ\sigma\circ M_{l-1} (\boldsymbol{x}).\]

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

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

\[\left|f_{l}^{+}(\boldsymbol{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,\boldsymbol{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,\boldsymbol{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}(\boldsymbol{w})=f_{i,2}^{-}\circ\sigma\circ M_{0}^{i}\circ f_{0}^{+}( \boldsymbol{w})\]

and

\[f(\boldsymbol{w})=f_{i,L+2}^{-}\circ M_{L}\circ f_{L}^{+}(\boldsymbol{w}).\]
Therefore, for all \(i\geq N_{\epsilon}\) and all \(\mathbf{w}\in[0,1]^{d}\)

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

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

### 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

\[\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], \tag{41}\]

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

\[\mathbb{E}\left[\ell(Q_{f^{\star}},Q_{\widehat{f}})\right] \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]\] \[\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], \tag{42}\]

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

\[p=38(\lfloor\alpha\rfloor+1)^{2}3^{d}d^{\lfloor\alpha\rfloor+1}N\lceil\log_{2}(8N )\rceil, \tag{43}\]

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

and \(K\) being large enough,

\[\inf_{f\in\overline{\mathcal{F}}_{(L,p,K)}}\|f^{\star}-f\|_{1,P_{W}} =\inf_{f\in\overline{\mathcal{F}}_{(L,p,K)}}\int_{\mathscr{W}}|f^{ \star}(w)-f(w)|dP_{W}(w) \tag{45}\] \[\leq 19B(\lfloor\alpha\rfloor+1)^{2}d^{\lfloor\alpha\rfloor+( \alpha\lor 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

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

where \(C_{d}\) only depends on \(d\) and \(C_{\alpha,d}\) only depends on \(d\) and \(\alpha\). Plugging (45) and (46) 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\). 

### 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,\mathbf{p})\) and \(f_{2}\in\overline{\mathcal{F}}(L^{\prime},\mathbf{p}^{\prime})\) be such that \(p_{L+1}=p_{0}^{\prime}\). Let \(\mathbf{v}\in\mathbb{R}^{p_{L+1}}\) be a vector. We define the composed network \(f_{2}\circ\sigma_{\mathbf{v}}(f_{1})\), where

\[\sigma_{\mathbf{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 \(\mathbf{y}=(y_{1},\ldots,y_{p_{L+1}})^{\top}\in\mathbb{R}^{p_{L+1}}\). Then \(f_{2}\circ\sigma_{\mathbf{v}}(f_{1})\) belongs to the space \(\overline{\mathcal{F}}(L+L^{\prime}+1,(\mathbf{p},p_{1}^{\prime},\ldots,p_{L+1}^{ \prime}))\).

_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,\mathbf{p})\) and \(f_{2}\in\overline{\mathcal{F}}(L,\mathbf{p}^{\prime})\), where \(p_{0}=p_{0}^{\prime}\). 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_{1}^{\prime},\ldots,p_{L+1}+p_{L+1}^{ \prime}))\).
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}^{*}\), \(\mathbf{d}=(d_{0},\ldots,d_{k})\in(\mathbb{N}^{*})^{k+1}\), \(\mathbf{t}=(t_{0},\ldots,t_{k})\in(\mathbb{N}^{*})^{k+1}\) with \(t_{i}\leq d_{i}\) and \(\boldsymbol{\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}}([0,1]^{t_{i}}\,,Q_{i})\) taking values in \([0,1]\) 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}:[0,1]^{t_{i}}\to[0,1]\),_

\[\|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_{i=i+1}^{k}(\alpha_{l}\wedge 1)},\]

_where \(|||f|||_{\infty}\) denotes the sup-norm of the function \(\boldsymbol{x}\mapsto|f(\boldsymbol{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 Holder 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\text{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}}([0,1]^{t_{0}}\,,Q_{0})\), \(g_{ij}\in\mathcal{H}^{\alpha_{i}}([0,1]^{t_{i}}\,,Q_{i})\), for \(i\in\{1,\ldots,k-1\}\) and \(g_{kj}\in\mathcal{H}^{\alpha_{k}}([0,1]^{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

\[\|\overline{g}_{ij}-g_{ij}\|_{\infty} \leq 19Q_{i}(\lfloor\alpha_{i}\rfloor+1)^{2}t_{i}^{\lfloor\alpha _{i}\rfloor+(\alpha_{i}\lor 1)/2}(N_{i}M_{i})^{-2\alpha_{i}/t_{i}}, \tag{47}\] \[\leq 19Q_{i}(\lfloor\alpha_{i}\rfloor+1)^{2}t_{i}^{\lfloor\alpha _{i}\rfloor+(\alpha_{i}\lor 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}\lor 0)\wedge 1=1-(1-\overline{g}_{ij})_{+}\). It is straightforward to observe that \(\widetilde{g}_{ij}\) assumes values in the interval \([0,1]\). 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}_{L_{i}}^{(i)}\circ\sigma\circ\cdots\circ\sigma \circ\overline{M}_{0}^{(i)},\]

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

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

where \(\widetilde{M}_{L_{i}}^{(i)}=M_{L_{i}+1}\circ\overline{M}_{L_{i}}^{(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 \([0,1]\) due to the transformation, this implies that

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

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}\text{ times}},\ldots,d_{k-1},\underbrace{d_{k}p_{k-1}, \ldots,d_{k}p_{k-1}}_{L_{k-1}\text{ 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 (47) and (48) yields the following
upper bound for the approximation error,

\[\inf_{f\in\overline{\mathcal{F}}\left(\overline{\mathcal{L}},(d_{0}, \overline{p},\ldots,\overline{p},d_{k+1})\right)}\|f^{\star}-f\|_{\infty}\] \[\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}\lor 1)/2}.\]

### 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\), \(\mathbf{d}\), \(\mathbf{t}\), \(\boldsymbol{\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

\[V(\overline{\mathcal{F}}_{(\overline{L},\overline{p},K)}) \leq C_{d_{0}}\overline{p}^{2}\overline{L}^{2}\log_{2}\left( \overline{p}\overline{L}^{2}\right) \tag{49}\] \[\leq C_{k,\mathbf{d},\mathbf{t},\boldsymbol{\alpha}}\left(\sum_{ i=0}^{k}L_{i}\right)^{2}\log_{2}\left(\sum_{i=0}^{k}L_{i}\right),\]

where \(C_{k,\mathbf{d},\mathbf{t},\boldsymbol{\alpha}}>0\) is a numerical constant depending only on \(k,\mathbf{d},\mathbf{t}\) and \(\boldsymbol{\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)})\),

\[\mathbb{E}\left[\ell(Q_{f^{\star}},Q_{\widehat{f}})\right] \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] \tag{50}\] \[\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

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

### 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_{\boldsymbol{\varepsilon}},\ \boldsymbol{\varepsilon}\in\{0,1\}^{D}\right\}\) satisfying_

1. _there exists_ \(\eta>0\) _such that for all_ \(\boldsymbol{\varepsilon},\boldsymbol{\varepsilon}^{\prime}\in\{0,1\}^{D}\)_,_ \[\|P_{\boldsymbol{\varepsilon}}-P_{\boldsymbol{\varepsilon}^{\prime}}\|_{TV} \geq\eta\delta(\boldsymbol{\varepsilon},\boldsymbol{\varepsilon}^{\prime}) \quad\text{with}\quad\delta(\boldsymbol{\varepsilon},\boldsymbol{\varepsilon}^ {\prime})=\sum_{j=1}^{D}\mbox{1}\!\!\!1_{\varepsilon_{j}\neq\varepsilon_{j}^{ \prime}}\] 2. _there exists a constant_ \(a\in[0,1/2]\) _such that_ \[h^{2}\left(P_{\boldsymbol{\varepsilon}},P_{\boldsymbol{\varepsilon}^{\prime}} \right)\leq\frac{a}{n}\quad\text{for all }\boldsymbol{\varepsilon},\boldsymbol{ \varepsilon}^{\prime}\in\{0,1\}^{D}\text{ satisfying }\delta(\boldsymbol{\varepsilon},\boldsymbol{\varepsilon}^{\prime})=1.\]

_Then for all measurable mappings \(\widehat{P}:\mathscr{X}^{n}\to\mathcal{P}\),_

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

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

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

\[\|P_{\boldsymbol{\varepsilon}}-P_{\overline{\boldsymbol{\varepsilon}}}\|_{TV} \leq\|P-P_{\boldsymbol{\varepsilon}}\|_{TV}+\|P-P_{\overline{\boldsymbol{ \varepsilon}}}\|_{TV}\leq 2\|P-P_{\boldsymbol{\varepsilon}}\|_{TV}.\]

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

\[\|P_{\boldsymbol{\varepsilon}}-P\|_{TV}\geq\frac{\eta}{2}\delta(\boldsymbol{ \varepsilon},\overline{\boldsymbol{\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)\mbox{1\kern-2.5pt{l}}_{\pi_{i}=0}\) and \(\ell_{i}^{\prime}(P)=(\eta/2)\mbox{1\kern-2.5pt{l}}_{\pi_{i}=1}\), for \(i\in\{1,\ldots,D\}\). Finally, the conclusion follows by applying a version of Assouad's lemma from Birge (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\operatorname*{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=\{0,h_{n},\ldots,(N_{n}-1)h_{n}\}\).

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)\mbox{1\kern-2.5pt{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 \([0,1]\). 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_{\mathbf{u}}\) on \([0,1]^{t^{*}}\) as

\[\psi_{\mathbf{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 \(\mathbf{u}=(u_{1},\ldots,u_{t^{*}})\in\mathcal{U}_{n}=\{(u_{1},\ldots,u_{t^{*} }),\;u_{i}\in\Lambda\}\). Note that for any \(\mathbf{u},\mathbf{u}^{\prime}\in\mathcal{U}_{n}\), \(\mathbf{u}\neq\mathbf{u}^{\prime}\), the supports of \(\psi_{\mathbf{u}}\) and \(\psi_{\mathbf{u}^{\prime}}\) are disjoint. For any \(\boldsymbol{\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^{\boldsymbol{\beta}}\psi_{\mathbf{u}}\|_{\infty}\leq 1\) due to the fact that \(\mathcal{K}\in\mathcal{H}^{\alpha^{*}}(\mathbb{R},1)\). Set \(\mathcal{I}_{\mathbf{u}}=[u_{1},u_{1}+h_{n}]\times\cdots\times[u_{t^{*}},u_{t^ {*}}+h_{n}]\). Moreover, for any \(\boldsymbol{\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 \(\boldsymbol{x},\boldsymbol{y}\in\mathcal{I}_{\mathbf{u}}\),

\[\frac{\left|\partial^{\boldsymbol{\beta}}\psi_{\mathbf{u}}(\boldsymbol{x})- \partial^{\boldsymbol{\beta}}\psi_{\mathbf{u}}(\boldsymbol{y})\right|}{\| \boldsymbol{x}-\boldsymbol{y}\|_{2}^{\alpha^{*}-\lfloor\alpha^{*}\rfloor}} \leq t^{*}.\]

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

\[\phi_{\boldsymbol{\varepsilon}}(w_{1},\ldots,w_{t^{*}})=\sum_{\mathbf{u}\in \mathcal{U}_{n}}\varepsilon_{\mathbf{u}}\psi_{\mathbf{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_{\boldsymbol{\varepsilon}}\in\mathcal{H}^{\alpha^{*}}(\left[0,1\right]^{t^ {*}},2t^{*})\).

Let \(d_{i}^{\prime}=\min\{d_{0},\ldots,d_{i}\}\), for all \(i\in\{0,\ldots,k\}\). For \(0\leq i<i^{*}\), we denote \(f_{i}(\boldsymbol{w})=(w_{1},\ldots,w_{d_{i+1}})^{\top}\), if \(d_{i+1}=d_{i+1}^{\prime}\); otherwise, we set \(f_{i}(\boldsymbol{w})=(w_{1},\ldots,w_{d_{i}^{\prime}},0,\ldots,0)^{\top}\). We denote \(f_{\boldsymbol{\varepsilon},i^{*}}(\boldsymbol{w})=(\phi_{\boldsymbol{ \varepsilon}}(w_{1},\ldots,w_{t^{*}}),0,\ldots,0)^{\top}\)
\(f_{i}(\mathbf{w})=(w_{1}^{\alpha_{i}\wedge 1},0,\ldots,0)^{\top}\), for \(i^{*}<i\leq k-1\) and \(f_{k}(\mathbf{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

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

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

Since \(W\) is uniformly distributed on \([0,1]^{d_{0}}\), we can compute

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

and

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

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

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

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

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

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_{\mathbf{\gamma}_{\mathbf{\varepsilon}}},\ \mathbf{\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^{*}\in\mathcal{F}(k,\mathbf{d},\mathbf{t},\mathbf{ \alpha},B)}\mathbb{E}\left[\ell(Q_{f^{*}},Q_{\widehat{f}})\right]\geq cn^{- \frac{{\alpha^{**}}}{2\alpha^{**}+t^{*}}}.\]