# Sup-Norm Convergence of Deep Neural Network Estimator for Nonparametric
Regression by Adversarial Training

Masaaki Imaizumi†‡ †The University of Tokyo, ‡RIKEN Center for Advanced
Intelligence Project

###### Abstract.

We show the sup-norm convergence of deep neural network estimators with a
novel adversarial training scheme. For the nonparametric regression problem,
it has been shown that an estimator using deep neural networks can achieve
better performances in the sense of the $L2$-norm. In contrast, it is
difficult for the neural estimator with least-squares to achieve the sup-norm
convergence, due to the deep structure of neural network models. In this
study, we develop an adversarial training scheme and investigate the sup-norm
convergence of deep neural network estimators. First, we find that ordinary
adversarial training makes neural estimators inconsistent. Second, we show
that a deep neural network estimator achieves the optimal rate in the sup-norm
sense by the proposed adversarial training with correction. We extend our
adversarial training to general setups of a loss function and a data-
generating function. Our experiments support the theoretical findings.

##  1\. Introduction

We study the nonparametric regression problem. Suppose we observe
$(X_{1},Y_{1}),...,(X_{n},Y_{n})\in[0,1]^{d}\times\mathbb{R}$ with dimension
$d\in\mathbb{N}$ that are independent and identical copies of a
$[0,1]^{d}\times\mathbb{R}$-valued random element $(X,Y)$ which follows the
following regression model:

$\displaystyle Y=f^{*}(X)+\xi,$ (1)

where $f^{*}:[0,1]^{d}\to\mathbb{R}$ is an unknown function, $\xi$ is a random
noise variable with zero mean and finite variance and is independent to $X$,
and $X$ follows a marginal measure $P_{X}$ on $[0,1]^{d}$. Our interest is to
utilize a deep neural network model and develop an estimator $\widehat{f}$
from the model and the $n$ observations, then study its estimation risk in
terms of the sup-norm, referred to as an $L^{\infty}$-risk:

$\displaystyle\sup_{x\in[0,1]^{d}}|\widehat{f}(x)-f^{*}(x)|,$ (2)

which implies uniform convergence of the estimator. In this study, we prove
that an adversarial training framework can provide an estimator with deep
neural networks whose $L^{\infty}$-risk converges, then derive a convergence
rate of the risk and show the minimax optimality of the rate.

###  1.1. Background and Question

Deep learning is a data-driven statistical method using deep neural network
models [36], which have multiple layers. It has many well-known extensions,
such as a deep convolutional network [33], a residual network [24], and an
attention mechanism [67]. Owing to the multiple layers and the well-designed
training algorithm, deep learning has achieved quite accurate prediction
performance in various tasks.

The framework of nonparametric regression has been actively used to analyze
deep neural networks, and many roles of deep learning have been revealed. A
deep neural network is a model of functions $f:[0,1]^{d}\to\mathbb{R}$ with
multiple layers such that

$\displaystyle f(x)=g_{L}\circ g_{L-1}\circ\cdots\circ g_{1}(x),$ (3)

where $g_{1}(\cdot),...,g_{L}(\cdot)$ are trainable functions by $L$ layers.
Deep learning is a method of fitting the function by deep neural networks to
observed data, hence it is obviously regarded as a method for the
nonparametric regression problem. Specifically, in most studies on the
nonparametric regression with deep neural networks, the following least-square
estimator has been studied:

$\displaystyle\widehat{f}^{\mathrm{LS}}\in\operatornamewithlimits{argmin}_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}(Y_{i}-f(X_{i}))^{2},$
(4)

where $\mathcal{F}$ is a set of functions by deep neural networks with the
form (3). Further, performance of the estimator $\widehat{f}^{\mathrm{LS}}$
has been studied by its $L^{2}$-risk

$\displaystyle\|\widehat{f}^{\mathrm{LS}}-f^{*}\|_{L^{2}}^{2}:=\mathbb{E}\left[(\widehat{f}^{\mathrm{LS}}(X)-f^{*}(X))^{2}\right].$
(5)

Using this framework, seminal works [3, 53, 32] show that the multilayer
structure of deep neural networks fits an internal structure of the unknown
function $f^{*}$ and that its estimation error achieves a faster convergence.
[12, 32, 56, 57] investigate statistical properties of the neural estimators
such as asymptotic distribution and robustness. [25, 26, 63, 58, 65] show that
the multilayer structure of the neural estimator is effective when the target
function $f^{*}$ has irregular properties such as discontinuity and
heterogeneous smoothness. [7, 45, 52, 29, 58] shows an adaptive property of
the neural estimators to an intrinsic low-dimensionality of the observations,
e.g., data concentrates on a low-dimensional manifold in its domain.

Studying a sup-norm value of the estimation error has been an important
interest in nonparametric regression problems. The sup-norm value, referred to
as an $L^{\infty}$-risk, is a sharper measure of accuracy and sensitivity of
estimators than the $L^{2}$-risk. Furthermore, the sup-norm convergence of
errors is useful for statistical inference, such as a uniform confidence band,
and is effective in the case with covariate shift of the transfer learning
[54]. For several conventional (non-deep) nonparametric estimators for
$f^{*}$, their sup-norm convergence has been actively studied. Classically,
the convergence of kernel methods [46, 55, 21, 14, 18] and series methods [8,
44, 11, 59, 5, 6, 2] have been investigated. More recently, the convergence of
wavelet methods [15, 17], methods with reproducing kernel Hilbert spaces [71],
and Gaussian process methods [4, 16, 23, 72] have been clarified. Roughly
speaking, when studying the sup-norm convergence of these non-deep estimators
$\widehat{f}^{\mathrm{ND}}$, the following linear-in-basis form plays an
effective role:

$\displaystyle\widehat{f}^{\mathrm{ND}}=\sum_{j\in J}w_{j}\psi_{j}(\cdot),$
(6)

where $J$ is an index set, $\\{w_{j}\\}_{j\in J}$ is a set of weights in
$\mathbb{R}$ trained by the least-square approach, and
$\\{\psi_{j}(\cdot)\\}_{j\in J}$ is a family of basis functions (possibly
depending on covariates) such as wavelets or kernels. Since the non-deep
estimators have the linear form, it is possible to control the
$L^{\infty}$-risk effectively and show its convergence, except a general
result by [54].

Our interest is to evaluate the $L^{\infty}$-risk of an estimator using deep
neural networks (10). Since the deep neural network model (3) does not have
the linear-in-basis form (6) as the non-deep methods, the existing analysis
cannot study the $L^{\infty}$-risk of deep neural networks. Based on the
background, we have the following questions:

Is it possible to achieve an estimator by deep neural networks $f^{*}$ whose
$L^{\infty}$-risk converges?
If so, is it possible to show the optimality of a convergence rate of the
$L^{\infty}$-risk?

###  1.2. Introduction to Adversarial Training

The adversarial training is a training scheme for deep neural networks, which
has been developed to deal with an adversarial attack on prediction by neural
networks. An adversarial attack is a methodology to mislead deep neural
networks in its predictions, by putting a tiny perturbation into a covariate
for a trained deep neural network. Since functions by trained deep neural
networks are unstable, the perturbed samples, called adversarial samples, vary
the outputs of deep neural networks drastically. [19] reported that the
phenomenon by introducing a case in which a deep neural network misclassified
an image of a panda as an image of gibbons by adding very fine noise to the
image. After the finding, many adversarial attack methods have been developed
[30, 64, 48, 43], threatening the robustness of neural networks.

A standard approach to adversarial training is to minimize a robustified
empirical risk, which is measured by adding perturbations to the observed
input variable [19, 48, 43]. Rigorously, an estimator by the adversarial
training for regression is defined as the minimizer of the following empirical
risk:

$\displaystyle\min_{f\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^{n}\max_{x^{\prime}:\|x^{\prime}-X_{i}\|_{\infty}\leq
h}(Y_{i}-f(x^{\prime}))^{2},$ (7)

with some $h>0$. The outer minimization is solved by the gradient descent
method as well as the usual least-square loss, and the inner maximization is
solved by a gradient ascent method. Several efficient algorithms have been
proposed to solve this problem effectively [70, 69, 76], such as the fast
gradient sign method [24, 30]. The optimization process is summarized in the
following:

  1. i.

Initialize $f\in\mathcal{F}$ and repeat the following steps ii and iii:

  2. ii.

For each $(Y_{i},X_{i})$, find
$x^{*}_{i}=\operatornamewithlimits{argmax}_{x^{\prime}\in\\{x:\|x-X_{i}\|_{\infty}\leq
h\\}}(Y_{i}-f(x^{\prime}))^{2}$.

  3. iii.

Update function $f\leftarrow
f-\eta\nabla(n^{-1}\sum_{i=1}^{n}(Y_{i}-f(x^{*}_{i}))^{2})$,

where $\eta>0$ is a learning rate and $\nabla$ denotes a derivative with
respect to neural network parameters of $f$. Note that the efficiency of the
algorithm is not a primary interest of this study, hence we focus on the
estimation error by the global minimizer of the adversarial risk.

Several works actively pursue a theoretical understanding of adversarial
training. One of the most significant issues is a trade-off between the
robustness and accuracy of the adversarial training, which studies the
possibility of balancing the predictive performance of deep neural networks
with their ability to defend against adversarial samples. A risk bound and the
sample complexity of the adversarial training in general settings is widely
examined [31, 60, 74, 13, 41, 73, 49]. The predictive performance of the
adversarial training has been also studied, particularly in linear regression
models with over-parameterization [28, 42, 50, 20].

###  1.3. This Study

The purpose of this study is to investigate the sup-norm convergence of an
error by deep neural networks using the adversarial training scheme. For this
aim, we develop a novel formulation of adversarial training and study its
efficiency. Specifically, our formulation includes a preprocessing for
smoothing the output variable at the first step, then formulates a neural
estimator as a minimizer of an empirical adversarial risk associated with the
preprocessing. The preprocessing has a role to reduce a bias on the estimator
from the perturbation of the adversarial training scheme. As a specific form
of preprocessing, we can employ several nonparametric estimators including the
nearest neighbor method and the kernel method.

As a result, we derive an upper bound on the $L^{\infty}$-risk of the
estimator with deep neural networks using our adversarial training scheme,
then reveal some properties of its convergence rate. Specifically, our
contributions are summarized as follows.

  * (i)

We derive a convergence rate of the $L^{\infty}$-risk of the estimator when
the true function $f^{*}$ belongs to the Hölder space. The derived rate
achieves the minimax optimal rate with an appropriately designed
preprocessing.

  * (ii)

We show the inconsistency of the ordinary adversarial training without
preprocessing. This is due to the inability of an output variable in the
regression problem to accommodate perturbations of the adversarial training.

  * (iii)

Our approach applies to not only the adversarial training with a squared loss
but also a general convex loss. Specifically, we study an $L^{\infty}$-risk of
the regression problem of general loss, which is useful for handling data that
have heavy-tailed noise.

  * (iv)

We additionally study the $L^{\infty}$-risk when the true function $f^{*}$ has
a heterogeneous smoothness, i.e. it belongs to the Besov space. Our analysis
shows the minimax optimality of the convergence rate of the $L^{\infty}$-risk
in this case.

  * (v)

Our result is applicable to a wide range of architectures of deep neural
networks, such as a fully-connected dense layer. Also, it allows both finite
depth networks and finite width networks.

We conduct numerical experiments and confirm that our theoretical results are
consistent with the result.

Our results provide new implications for the understanding of adversarial
training, which argues the trade-off between robustness and accuracy of
prediction by adversarial training. Along with this line, we show that (i) the
ordinary adversarial learning is not consistent in the regression problem in
the first place, (ii) the robustness obtained by adversarial learning is
described by sup-norm convergence of the estimation error, and (iii) the
adversarial training achieve the optimal rate with appropriate preprocessing.

Technical contributions in our proof are summarized as follows. First, we
derive an upper bound of the sup-norm of an estimation error by the
adversarial risk up to constants. This bound uses a volume of a neighborhood
set of an input variable, which is utilized to design the adversarial
perturbation. Second, we develop an empirical process technique for the
evaluation of preprocessing. To control the effects of the preprocessing and
the adversarial training simultaneously, we involve two levels of evaluation
of biases and variances as appropriate.

###  1.4. Organization

The rest of this paper is organized as follows. Section 2 gives a setup for
the nonparametric regression problem and the definition of deep neural
networks. Section 3 gives a general formulation of adversarial training and an
overview of analysis on it. Furthermore, the section shows that naive
adversarial training does not give a consistent estimator. In Section 4, as a
main result, we derive an upper bound by a sup-norm of an estimation error by
the developed estimator Section 5 gives extensions and applications. Section 6
gives numerical simulations, and Section 7 concludes.

###  1.5. Notation

For $n\in\mathbb{N}$, $[n]:=\\{1,2,...,n\\}$ is a set of natural numbers no
more than $n$. For $a,a^{\prime}\in\mathbb{R}$, $a\vee
a^{\prime}:=\max\\{a,a^{\prime}\\}$ is the maximum. $\lfloor a\rfloor$ denotes
the largest integer which is no more than $a$. The Euclidean norm of a vector
$b\in\mathbb{R}^{d}$ is denoted by $\|b\|_{2}:=\sqrt{b^{\top}b}.$ Let $C_{w}$
be a positive finite constant depending on a variable $w$. $\textbf{1}\\{E\\}$
denotes the indicator function. It is $1$ if the event $E$ holds and $0$
otherwise. For a matrix $A\in\mathbb{R}^{N\times N}$, $A_{i,j}$ denotes an
$(i,j)$-th element of $A$ for $i,j=1,...,N$. For a measurable function
$f:\Omega\to\mathbb{R}$ on a set $\Omega\subset\mathbb{R}^{d}$,
$\|f\|_{L^{p}}(\mu):=(\int|f(x)|^{p}d\mu(x))^{1/p}$ denotes an $L^{p}$-norm
for $p\in[1,\infty)$ with a measure $\mu$, and
$\|f\|_{L^{\infty}}:=\sup_{x\in\Omega}|f(x)|$ denotes a sup-norm. Also,
$L^{p}(\Omega)$ denotes a set of measurable functions such that
$\|f\|_{L^{p}(\lambda)}<\infty$ with the Lebesgue measure $\lambda$. For
$x\in\mathbb{R}^{d}$, $\delta_{x}$ denotes the Dirac measure at $x$. For a
function $f:\mathbb{R}^{d}\to\mathbb{R}$ with a multi-variate input
$(x_{1},...,x_{d})\in\mathbb{R}^{d}$ and a multi-index
$a=(a_{1},...,a_{d})\in\mathbb{N}^{d}$,
$\partial^{a}f(x_{1},...,x_{d}):=\partial_{x_{1}}^{a_{1}}\partial_{x_{2}}^{a_{2}}\cdots\partial_{x_{d}}^{a_{d}}f(x_{1},...,x_{d})$
denotes a partial derivative with the multi-index. For a variable $x$, $C_{x}$
denotes some positive finite constant that polynomially depends on $x$, and it
can have different values in different places. For sequences of reals
$\\{a_{n}\\}_{n\in\mathbb{N}}$ and $\\{b_{n}\\}_{n\in\mathbb{N}}$,
$a_{n}\asymp b_{n}$ denotes $\lim_{n\to\infty}a_{n}/b_{n}\to c$ with some
$c\in(0,\infty)$, $a_{n}=O(b_{n})$ denotes $|a_{n}|\leq M|b_{n}|$ and
$a_{n}=\Omega(b_{n})$ denotes $|a_{n}|\geq M|b_{n}|$ with some $M>0$ for all
sufficiently large $n$. $a_{n}=o(b_{n})$ denotes $|a_{n}|\leq M|b_{n}|$ for
any $M>0$ and for all sufficiently large $n$. $\tilde{O}(\cdot)$ and
$\tilde{\Omega}(\cdot)$ are the notations ${O}(\cdot)$ and ${\Omega}(\cdot)$
ignoring multiplied polynomials of $\log(n)$, respectivelly. For a sequence of
random variables $\\{X_{n}\\}_{n\in\mathbb{N}}$, $X_{n}=O_{P}(a_{n})$ denotes
$\mathrm{Pr}(|X_{n}/a_{n}|>M)\leq\varepsilon$ for any $\varepsilon>0$ and some
$M>0$ for all sufficiently large $n$, and $X_{n}=o_{P}(a_{n})$ denotes
$\lim_{n\to\infty}\mathrm{Pr}(|X_{n}/a_{n}|>\varepsilon)=0$ for any
$\varepsilon>0$.

##  2\. Problem Setting and Preliminaries

###  2.1. Nonparametric Regression and $L^{\infty}$-Risk

####  2.1.1. Model and Observations

For the nonparametric regression, suppose that we have $n$ observations
$(X_{1},Y_{1}),...,(X_{n},Y_{n})\in[0,1]^{d}\times\mathbb{R}$ that are
independent and identical copies of a random variable $(X,Y)$ which follows
the regression model (1). Note that the model is characterized by the unknown
function $f^{*}$ and the noise variable $\xi$. Let $P_{X}$ be a marginal
measure of $X$.

####  2.1.2. Basic Assumption

We introduce a standard assumption on the regression model.

######  Assumption 1.

$P_{X}$ has a density function that is uniformly lower bounded by
$C_{P_{X}}>0$ on $[0,1]^{d}$.

Assumption 1 is important to estimate $f^{*}$ on the entire domain
$[0,1]^{d}$. Both of the assumptions are commonly introduced in the
nonparametric regression for neural networks [3, 53].

We suppose that $f^{*}$ belongs to a function class with the Hölder smoothness
with an index $\beta>0$. To the end, we define a ball of the Hölder space with
$\beta>0$ as

$\displaystyle\mathcal{H}^{\beta}([0,1]^{d})$
$\displaystyle:=\Biggl{\\{}f:[0,1]^{d}\to\mathbb{R}\mid$ (8)
$\displaystyle\qquad\sum_{b\in\mathbb{N}^{d}:\|b\|_{1}<\lfloor\beta\rfloor}\|\partial^{b}f\|_{L^{\infty}}+\sum_{b\in\mathbb{N}^{d}:\|b\|_{1}=\lfloor\beta\rfloor}\sup_{x,x^{\prime}\in[0,1]^{d},x\neq
x^{\prime}}\frac{|\partial^{b}f(x)-\partial^{b}f(x^{\prime})|}{\|x-x^{\prime}\|_{\infty}^{\beta-\lfloor\beta\rfloor}}\leq
B\Biggr{\\}},$ (9)

with its radius $B\geq 1$. Intuitively, $\mathcal{H}^{\beta}([0,1]^{d})$ is a
set of functions on $[0,1]^{d}$ that are $\lfloor\beta\rfloor$ times partially
differentiable and their derivatives are $(\beta-\lfloor\beta\rfloor)$-Hölder
continuous.

######  Assumption 2.

There exists $\beta>0$ such that
$f^{*}\in\mathcal{H}^{\beta^{\prime}}([0,1]^{d})$ holds for all
$\beta^{\prime}\in(0,\beta]$.

To impose differentiability for $f^{*}$ is the usual setting for nonparametric
regression (see [66], for example). Further, in the statistical studies on
deep neural networks, it has also studied the estimation of functions with
more complex structures [3, 53, 26, 63]. We will discuss an extension on this
assumption in Section 5.

####  2.1.3. Goal: Sup-norm Convergence

Our goal is to estimate the true function $f^{*}$ in the model (1) and study
an estimation error of an estimator in terms of the sup-norm
$\|\cdot\|_{L^{\infty}}$. Rigorously, we will develop an estimator
$\widehat{f}$ and study its $L^{\infty}$-risk defined as follows:

$\displaystyle\|\widehat{f}-f^{*}\|_{L^{\infty}}:=\sup_{x\in[0,1]^{d}}|\widehat{f}(x)-f^{*}(x)|.$
(10)

The $L^{\infty}$-risk is a sharp measure for the robustness of estimators and
is applied to statistical inference such as a uniform confidence band. To
understand this point, we discuss its relation to the commonly used
$L^{2}$-risk measured by the $L^{2}$-norm, which is a typical case with the
following $L^{p}$-norm ($p\in[1,\infty)$) with $p=2$:

$\displaystyle\|\widehat{f}-f^{*}\|_{L^{p}(P_{X})}^{p}:=\mathbb{E}_{X}\left[|\widehat{f}(X)-f^{*}(X)|^{p}\right].$
(11)

Since the $L^{\infty}$-risk bounds the $L^{p}$-risk, i.e.
$\|\widehat{f}-f^{*}\|_{L^{\infty}}\geq\|\widehat{f}-f^{*}\|_{L^{p}(P_{X})}$
holds for every $p\geq 1$, the $L^{\infty}$-risk leads stronger convergence.
Figure 1 illustrates the difference between the convergences in the
$L^{2}$-norm and the sup-norm. In the related studies with neural networks
(e.g. [3, 53]), the $L^{2}$-risk has been mainly studied, but the
$L^{\infty}$-risk of neural network estimators has not been proved to
converge.

Convergence in $L^{2}$-norm

Convergence in sup-norm

Figure 1. Examples of the $L^{2}-$ and $L^{\infty}$-risks. The black curve is
the true function $f^{*}$ and the red curve is an estimator. In the left, the
$L^{2}$-risk is determined by the volume of the difference between the two
functions. Even if the estimator is unstable for a particular input, the
$L^{2}$-risk is still small. In the right, the $L^{\infty}$-risk is determined
by the maximum distance between the two functions at a given input point. When
the $L^{\infty}$-risk is small, the two functions have similar shapes.

###  2.2. Deep Neural Network Model

We define a deep neural network, which is a model of functions by multiple
layers. Specifically, we consider deep neural networks with fully-connected
layers and the rectified linear unit (ReLU) activation function, which is one
of the most commonly used activations.

Let $L\in\mathbb{N}$ be a number of layers, and
$\mathcal{W}=(W_{1},...,W_{L+1})\in\mathbb{N}^{L+1}$ be a tuple of width
parameters, where $W_{\ell}$ denotes width of an $\ell$-th layer. Deep neural
networks have a weight matrix $A_{\ell}\in\mathbb{R}^{W_{\ell+1}\times
W_{\ell}}$ and a weight vector $b_{\ell}\in\mathbb{R}^{W_{\ell}}$ for each
$\ell\in[L]$. For each $d\in\mathbb{N}$, we introduce a ReLU activation
function $\sigma:\mathbb{R}^{d}\to\mathbb{R}^{d}$ such that
$\sigma(z)=((z_{1}\vee 0),(z_{2}\vee 0),...,(z_{d}\vee 0))^{\top}$ for
$z=(z_{1},...,z_{d})\in\mathbb{R}^{d}$. For each $\ell\in[L-1]$, we define a
map $g_{\ell}:\mathbb{R}^{W_{\ell}}\to\mathbb{R}^{W_{\ell+1}}$ by an $\ell$-th
layer as

$\displaystyle
g_{\ell}(z)=\sigma\left(A_{\ell}z+b_{\ell}\right),~{}z\in\mathbb{R}^{W_{\ell}}.$
(12)

For the last $L$-th layer, we define $g_{L}(z)=A_{L}z+b_{L}$ with
$z\in\mathbb{R}^{W_{L}}$. For $L$ and $\mathcal{W}$, we define a parameter
space $\Theta_{L,\mathcal{W}}:=(\mathbb{R}^{W_{2}\times
W_{1}}\times\mathbb{R}^{W_{1}})\times(\mathbb{R}^{W_{3}\times
W_{2}}\times\mathbb{R}^{W_{2}})\times\cdots\times(\mathbb{R}^{W_{L+1}\times
W_{L}}\times\mathbb{R}^{W_{L}})$ whose elements is
$\theta=((A_{1},b_{1}),(A_{2},b_{2}),...,(A_{L},b_{L}))$, then we define a
function $g:\mathbb{R}^{d}\to\mathbb{R}$ by a deep neural network with
$d=W_{1}$ and $W_{L+1}=1$ as

$\displaystyle f_{\theta}(x)=g_{L}\circ g_{L-1}\circ\cdots\circ
g_{1}(x),~{}x\in[0,1]^{d}.$ (13)

Intuitively, $f_{\theta}(x)$ is constituted by compositions of $L$ maps by the
multiple layers with the maximum width
$\|\mathcal{W}\|_{\infty}=\max_{\ell\in[L+1]}W_{\ell}$. There are at most
$\sum_{\ell=1}^{L}(W_{\ell}+1)W_{\ell+1}\leq
L(\|\mathcal{W}\|_{\infty}+1)^{2}$ parameters in the deep neural network
model.

We introduce a set of functions by deep neural networks with $L$ layers and
$W$ maximum width. With a tuple $(L,W)\in\mathbb{N}^{2}$ and an upper bound
$B\geq 1$, we define the set of functions by deep neural networks as

$\displaystyle\mathcal{F}(L,W):=\Bigl{\\{}f_{\theta}\mbox{~{}as~{}\eqref{def:DNN}}\mid\|f_{\theta}\|_{L^{\infty}}\leq
B,\theta\in\Theta_{L,\mathcal{W}},\|\mathcal{W}\|_{\infty}\leq W\Bigr{\\}}.$
(14)

The condition on the upper bound $B$ can be satisfied by a clipping operation
using the ReLU activation function [63].

This definition of deep neural networks includes several variations of neural
networks. If the parameter matrix $A_{\ell}$ is not sparse, the defined neural
network is a fully-connected neural network. If the matrix $A_{\ell}$ is
constrained to be sparse with some structure, it is equivalent to a
convolutional neural network [33] or a residual network [24].

######  Remark 1.

One advantage of the definition (14) is that it controls the easily
manipulated values of width $W$ and depth $L$ of neural networks, that can be
easily specified when designing neural network models. This is in contrast to
manipulating the number of nonzero parameters and the maximum parameter value,
which are difficult to control in practice (for example, see [53]).

##  3\. Adversarial Training Estimator for Regression

###  3.1. Ordinary Adversarial Training and its Inconsistency

We introduce a framework of adversarial training. The adversarial training
framework defines its loss using an input point in the neighborhood of a data
point that maximizes loss, as reviewed in (7). Rigorously, with a scale
multipliers $h\in(\underline{h},1)$ with $\underline{h}>0$, we consider a
neighbourhood of $x\in[0,1]^{d}$ as

$\displaystyle\Delta_{h}^{p}(x)=\\{x^{\prime}\in[0,1]^{d}\mid\|x-x^{\prime}\|_{p}\leq
h\\}\subset[0,1]^{d}.$ (15)

Then, we consider the following estimator by the empirical adversarial risk
with a function $f:[0,1]^{d}\to\mathbb{R}$ and $p\geq 1$:

$\displaystyle
R_{n}^{\mathrm{o}}(f):=\frac{1}{n}\sum_{i=1}^{n}\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}(Y_{i}-f(x^{\prime}))^{2}.$
(16)

We can define an estimator of $f^{*}$ by the minimizer of this empirical
adversarial risk as

$\displaystyle\check{f}:=\operatornamewithlimits{argmin}_{f\in\mathcal{F}(L,W)}R_{n}^{\mathrm{o}}(f).$
(17)

The minimax optimization in the problem (16) is solved by various algorithms
[24, 30, 43].

####  3.1.1. Inconsistency of Ordinary Adversarial Training

In this section, we show the inconsistency of $\widetilde{f}$ by ordinary
adversarial training. Specifically, we obtain the following result.

######  Proposition 1.

Suppose $n\geq 3$. There exists a sub-Gaussian noise $\xi_{i}$,
$f^{*}\in\mathcal{H}^{1}([0,1]^{d})$, $P_{X}$, and $h\in(0,1)$ such that the
estimator $\check{f}$ in (16) satisfies the following inequality with an
existing constant $c^{*}>0$ with probability at least 0.5:

$\displaystyle\|\check{f}-f^{*}\|_{L^{2}(P_{X})}^{2}\geq c^{*}.$ (18)

This result shows that the $L^{\infty}$-risk of $\check{f}$ does converge to
zero with the ordinary adversarial training, regardless of the sample size $n$
and a neural network architecture. Since the $L^{\infty}$-risk is bounded
below by the $L^{2}$-risk, hence the ordinary adversarial training also yields
an inconsistent estimator in the sense of a sup-norm. This result is not
limited to the choice of model used for the estimator, hence it occurs with
methods other than neural networks.

Intuitively, ordinary adversarial training produces a bias by the design of
perturbations on inputs (see the middle panel of Figure 2). This is because
the perturbation makes $\check{f}(X_{i})$ fit to an output with a shift
$\varsigma=x^{\prime}-X_{i}$, which creates the inconsistency. Hence, we need
to correct the bias by the ordinary adversarial training in the regression
problem.

###  3.2. Proposed Framework of Adversarial Training

We introduce an empirical risk function for adversarial training based on a
quadratic loss. We develop a random map $\widehat{Y}:[0,1]^{d}\to\mathbb{R}$
for surrogate outputs, which referred to a preprocessed output. This notion is
a general expression of several methods, and its specific configurations will
be given later. With $\widehat{Y}$, we define an empirical preprocessed
adversarial risk as

$\displaystyle
R_{n}(f):=\frac{1}{n}\sum_{i=1}^{n}\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}(\widehat{Y}(x^{\prime})-f(x^{\prime}))^{2},$
(19)

for a function $f\in L^{2}([0,1]^{d})$. This loss function is a generalized
version of the ordinary adversarial risk (19) with the preprocessing
$\widehat{Y}$. Using this notion, we define an estimator as the minimizer of
the empirical risk as

$\displaystyle\widehat{f}\in\operatornamewithlimits{argmin}_{f\in\mathcal{F}(L,W)}R_{n}(f).$
(20)

This framework intends to perturb an output variable in response to the
perturbation on the input $X_{i}$. That is, when the input point $X_{i}$ is
shifted by $\varsigma=x^{\prime}-X_{i}$ due to the adversarial training, we
also shift the output side by $\varsigma$. Hence, the observed outputs may not
be able to accommodate the shift. To address this issue, we prepare the
corresponding output using a preprocessing approach, such as the nearest
neighbor method. Figure 2 illustrates differences between the least square
estimator $\widehat{f}^{\mathrm{LS}}$, the ordinary adversarial training
$\check{f}$, and our proposal estimator by the adversarial training with
preprocessing $\widehat{f}$.

Least-square $\widehat{f}^{\mathrm{LS}}$

Ordinary adversarial training $\check{f}$

Our estimator $\widehat{f}$

Figure 2. Comparison of the estimators. The left is the least square
estimator, which measures the difference between $Y_{i}$ and $f(X_{i})$. The
middle is the ordinary adversarial training, measuring the difference between
$Y_{i}$ and $f(x^{\prime})$, where $x^{\prime}$ is chosen from a neighborhood
$\Delta_{h}^{p}(X_{i})$. The input is shifted to the right, which causes the
inconsistency. The right is adversarial training with preprocessing. For
$x^{\prime}\in\Delta_{h}^{p}(X_{i})$, it construct the corresponding
preprocessing $\widehat{Y}(x^{\prime})$ and measure the difference between
$\widehat{Y}(x^{\prime})$ and $f(x^{\prime})$.

####  3.2.1. Preprocessing Design

We impose the following assumptions on the preprocessing.

######  Assumption 3 (Preprocessing).

$\widehat{Y}(x)$ is continuous and
$\mathbb{E}[\|\widehat{Y}\|_{L^{\infty}}^{2}]\leq V^{2}$ with some $V>0$.
Also, there exists a non-negative sequence $\\{\zeta_{n}\\}_{n\in\mathbb{N}}$
such that $\zeta_{n}\to 0$ as $n\to\infty$ such that the following holds for
all $n\in\mathbb{N}$:

$\displaystyle\zeta_{n}^{2}\geq\mathbb{E}\left[\|\widehat{Y}-f^{*}\|_{L^{\infty}}^{2}\right].$
(21)

The sequence $\\{\zeta_{n}\\}_{n\in\mathbb{N}}$ represents a convergence rate
of the preprocessing $\widehat{Y}$ to $f^{*}$. Importantly, the data used to
construct the preprocessed output $\widehat{Y}$ here may overlap the data for
the estimator as (20). There are several examples for preprocessing as
follows.

######  Example 1 (Nearest neighbour).

First, we consider the $k$-nearest neighbor method. For $k\in\mathbb{N}$ and
$x\in[0,1]^{d}$, we define a radius
$B_{x}(r):=\\{x^{\prime}\in[0,1]^{d}\mid\|x-x^{\prime}\|_{2}\leq r\\}$ with
$r>0$, the $k$-nearest neighbour radius
$r_{k}(x):=\inf\\{r>0\mid|B_{x}(r)\cap\mathcal{D}|\geq k\\}$, and its
corresponding dataset $N_{k}(x):=B_{x}(r)\cap\mathcal{D}$. With this notion,
we define the $k$\- nearest neighbor preprocessing.

$\displaystyle\widehat{Y}(x)=\frac{1}{|N_{k}(x)|}\sum_{i=1}^{n}Y_{i}\textbf{1}\\{X_{i}\in
N_{k}(x)\\}$ (22)

In this example, if Assumption 2 holds with $\beta\in(0,1]$, we have
$\zeta_{n}^{2}=O(n^{-2\beta/(2\beta+d)}\log n)$ with $k\asymp
n^{2\beta/(2\beta+d)}$ by Theorem 1 in [27].

######  Example 2 (Posterior mean by Bayesian method).

We consider a mean of a posterior distribution by a prior distribution on
functions. The method considers a B-spline series (see [51] for overview and
specific constructions). With some tuple of numbers of basis
$(J_{1},...,J_{d})\in\mathbb{N}^{d}$ and orders
$(q_{1},...,q_{d})\in\mathbb{N}^{d}$, we consider parameters
$\\{\theta_{j_{1},...,j_{d}}\\}_{j_{1},...,j_{d}=1}^{J_{1},...,J_{d}}$ and the
B-spline series $\\{B_{j_{k},q_{k}}(x)\\}_{j_{k}=1}^{J_{k}}$ for $k=1,...,d$.
Then, the method constructs a prior distribution on a function $f$ with the
form

$\displaystyle
f(x)=\sum_{j_{1}=1}^{J_{1}}\cdots\sum_{j_{d}=1}^{J_{d}}\theta_{j_{1},...,j_{d}}\prod_{k=1}^{d}B_{j_{k},q_{k}}(x_{k}),$
(23)

by putting a Gaussian prior on the parameters $\theta_{j_{1},...,j_{d}}$. If
Assumption 2 holds with $\beta>0$, Theorem 4.4 in [72] shows that
$\zeta_{n}^{2}=O(n^{-2\beta/(2\beta+d)}\log^{2\beta/(2\beta+d)}n)$, which is
implied by a contraction of the posterior shown by the theorem.

We can pick other methods for preprocessing. The required property is that an
error in estimating a smooth function converges in the sup-norm sense.

##  4\. Main Result: $L^{\infty}$-Risk Analysis

We present our main results on the consistency of the estimator and a non-
asymptotic upper bound on the estimation error with its convergence rate in
$n$. We further discuss the minimax optimality of the obtained convergence
rate. To achieve optimality, we need to discuss the design of the
preprocessing $\widehat{Y}$ and the architecture of deep neural networks.

###  4.1. Consistency

We present an upper bound of an expectation of the $L^{\infty}$-risk of the
estimator. The first result is consistency in the sense of the
$L^{\infty}$-risk. In an asymptotic analysis with $n\to\infty$, a product of
the depth and width of deep neural networks should also increase in $n$.

######  Theorem 2.

Consider the regression model (1) and the adversarial estimator $\widehat{f}$
in (20) with the function class by deep neural networks with a tuple $(L,W)$.
Suppose 1, and 3 hold and $f^{*}$ is continuous. Then, there exists a tuple
$(L,W)$ with $LW=o(n)$ such that it holds that

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]\to
0,$ (24)

as $n\to\infty$.

The results show that under divergent widths and depths and appropriate
preprocessing, we obtain consistency in the sense of sup-norm. Note that
$f^{*}$ needs only be continuous, and conditions on derivatives are not
necessary. Also, it provides the following important implications: (i) we can
control the $L^{\infty}$-risk even though the deep neural network model does
not have the linear-in-feature structure, and (ii) the preprocessing solves
the problem of inconsistency in adversarial training presented in Section
3.1.1. Its proof is based on the procedure in Section 4.3.

We note the importance of sup-norm convergence in the context of estimation.
In the theory of approximation, the sup-norm convergence by neural networks
has been an important topic, that is,
$\inf_{f\in\mathcal{F}(L,W)}\|f-f^{*}\|_{L^{\infty}}\to 0$ as $L\to\infty$ or
$W\to\infty$, and numerous studies have studied the problem, e.g. [9, 37, 38].
Conversely, in the nonparametric regression problem, the sup-norm convergence
has been difficult due to noise in observations. Theorem 2 shows that the
adversarial training with preprocessing enables convergence in the sup-norm.

###  4.2. Non-Asymptotic Bound and Convergence Rate

As a more rigorous error evaluation, we derive a non-asymptotic upper bound
for the $L^{\infty}$-risk of the estimator with the adversarial training. This
result is also useful in studying convergence rates of the risk and discussing
its optimality.

######  Theorem 3.

Consider the regression model (1) and the adversarial estimator $\widehat{f}$
in (20) with the function class $\mathcal{F}(L,W)$ by deep neural networks.
Suppose Assumption 1, 2, and 3 hold for some $\beta>0$. Then we have

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]\leq
C_{P_{X},p,d,B,d,\beta}h^{-d}\left(\frac{(WL)^{2}\log(WL)\log
n}{n}+(WL)^{-4\beta/d}+h^{-d}\zeta_{n}^{2}\right),$ (25)

for every $n\geq\bar{n}$ with some $\bar{n}\in\mathbb{N}$.

This result gives some implications: (i) we develop an upper bound on the
$L^{\infty}$-risk of the estimator, and (ii) the bound is proportional to
$h^{-d}$, which appears when evaluating the $L^{\infty}$-risk using the
adversarial loss. Note that we can select $h$ as strictly positive and thus it
does not affect an order of the bound in $n$.

More precisely, this upper bound consists of the three terms. The first term
$O((WL)^{2}\log(WL)/n)$ is the complexity error, the second term
$O((WL)^{-4s/d})$ is the approximation error by the deep neural network, and
the third term $O(\zeta_{n}^{2})$ is the error by the preprocessing. The
complexity and approximation errors also appear in several risk bounds on an
$L^{2}$-risk of deep neural network (e.g., Theorem 4.3 in [57]). In contrast,
the preprocessing error term is a new term needed to derive an upper bound on
the $L^{\infty}$-risk.

We derive the convergence rate of the $L^{\infty}$-risk with respect to $n$.
Specifically, we select the width and depth of deep neural networks in order
to balance the trade-off in the error terms presented in Theorem 3.

######  Corollary 4.

Consider the setting in Theorem 3. Further, suppose that
$\zeta_{n}^{2}=O(n^{-2\beta/(2\beta+d)}\log^{\beta^{*}}n)$ for some
$\beta^{*}>0$. We set $L$ and $W$ as $LW\asymp n^{2\beta/(2\beta+d)}$. Then,
we obtain the following as $n\to\infty$:

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]=O\left(n^{-2\beta/(2\beta+d)}\log^{2\vee\beta^{*}}n\right).$
(26)

The rate obtained in Corollary 4 is identical to the minimax optimal rate of
risk measured in the sup-norm in the problem of estimating a function from
$\mathcal{H}^{\beta}([0,1]^{d})$ [61, 62]. Specifically, the derived rate
corresponds to the following lower bound:

$\displaystyle\inf_{\bar{f}_{n}}\sup_{f^{*}\in\mathcal{H}^{\beta}([0,1]^{d})}\mathbb{E}\Bigl{[}\|\bar{f}_{n}-f^{*}\|_{L^{\infty}}^{2}\Bigr{]}=\widetilde{\Omega}\left(n^{-2\beta/(2\beta+d)}\right),~{}(n\to\infty),$
(27)

where $\bar{f}_{n}$ is taken from all estimators depending on the $n$
observations. Since the derived rate is the same as the lower bound, we show
that the adversarial training estimator achieves the minimax optimal rate.

###  4.3. Proof Overview

We give an overview of proof of the main theorem. As preparation, we introduce
several notations related to adversarial training. With $h$, an order $p$ and
a base measure $P$, we define an adversarial (pseudo-)norm of
$f:[0,1]^{d}\to\mathbb{R}$ and its empirical analogue

$\displaystyle\|f\|_{P,\Delta}^{2}:=\mathbb{E}_{X\sim
P}\left[\max_{x^{\prime}\in\Delta_{h}^{p}(X)}|f(x^{\prime})|^{2}\right],\mbox{~{}~{}and~{}~{}}\|f\|_{n,\Delta}^{2}:=n^{-1}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}|f(x^{\prime})|^{2}.$
(28)

These norms correspond to the adversarial risks with a squared loss for the
regression problem ([28]). We also define an approximation error of deep
neural networks in $\mathcal{F}(L,W)$ as

$\displaystyle\Phi_{L,W}:=\inf_{f\in\mathcal{F}(L,W)}\|f-f^{*}\|_{L^{\infty}}.$
(29)

This term represents an expressive power of neural networks in
$\mathcal{F}(L,W)$, which decreases as $L$ or $W$ increase (see [39] for an
example). We further use a uniform covering number of $\mathcal{F}(L,W)$. Let
$Q_{n}$ be an empirical measure with $n$ samples. Given $\delta\in(0,1]$, we
define a $\delta$-covering set of $\mathcal{F}(L,W)$ as
$\\{f_{1},...,f_{N}\\}\subset\mathcal{F}$ and the uniform covering number from
the empirical process theory (e.g., [68]):

$\displaystyle
N_{L,W}(\delta):=\sup_{Q_{n}}N(\delta,\mathcal{F}(L,W),\|\cdot\|_{L^{2}(Q_{n})}),$
(30)

where the supremum is taken over all possible empirical measures $Q_{n}$. This
notion is useful to evaluate the complexity of the set of deep neural
networks, because it gives an upper bound without boundedness or sparsity of
parameters of neural networks (See Lemma 16, for example).

Our proof consists of three main elements: (i) the derivation of an upper
bound of the adversarial norm of the estimation error, (ii) to develop an
upper bound of the $L^{\infty}$ norm of the estimation error by the
adversarial norm, and (iii) a comb of the above results using the localization
technique. Each of these is described below.

In the first step, we derive an upper bound for the adversarial norm of the
estimation error. Rigorously, Lemma 10 will state the following upper bound

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\right]\leq
C\left\\{\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{n,\Delta}^{2}\right]+\frac{B^{2}(\log
N_{L,W}(\delta)+1)}{n}+\delta B+\delta^{2}\right\\},$ (31)

for any $\delta\in(0,1)$ with some universal constant $C>0$. Furthermore,
Proposition 12 will bound the empirical adversarial norm
$\mathbb{E}[\|\widehat{f}-f^{*}\|_{n,\Delta}^{2}]$ as

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{n,\Delta}^{2}\right]\leq
C\left\\{\left(\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]^{1/2}+\delta\right)\left(\frac{\log
N_{L,W}(\delta)}{n}+\zeta_{n}\right)^{1/2}+(\Phi_{L,W}+\zeta_{n})^{2}\right\\}.$
(32)

We achieve these bounds by extending the empirical process technique by [53]
to the adversarial norm. There are several points for noting: (i) the term
$\Phi_{L,W}$ represents a bias, and the term $O(\log N_{L,W}(\delta)/n)$
represents a variance of the estimator, that are similar to the least square
estimator, (ii) the variance term is described by the uniform covering number,
which is useful to study neural networks whose parameters are unbounded and
non-sparse, and (iii) there is a term $\zeta_{n}$ which represents the error
by the preprocessing, unlike the case of the least square estimator.

In the second step, we construct an upper bound for the sup-norm using the
adversarial norm. That is, we develop the following statement:

######  Lemma 5.

Consider the estimator as (20) and the adversarial norm as (28). Suppose
$P_{X}$ satisfies Assumption 1. Then, we have

$\displaystyle\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\geq
C_{P_{X},p,d}h^{d}\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}.$ (33)

Intuitively, we utilize the similarity between the adversarial norm and the
sup-norm to achieve the result. That is, the maximization over
$\Delta_{h}^{p}$ in the adversarial norm has a similar property to the sup-
norm. Using this property, we give an upper bound on the sup-norm while taking
into account the volume of the hypercube. We will give a generalized version
of this result as Lemma 15 in the supplementary material.

In the last step, we combine these results and derive the main statement of
Theorem 3. Here we apply the peeling argument to obtain convergence rates.
Note that a simple combination of the above results would lose optimality. To
obtain the minimax optimal rate, we evaluate the approximation error and the
uniform covering number based on the localization techniques.

##  5\. Applications

###  5.1. Extension to General Loss Function

####  5.1.1. Motivation and Setting

We can extend our adversarial training results to the case of non-squared loss
functions. Specifically, we can handle loss functions such as absolute value
loss, quantile loss, and Huber loss, which are used in the presence of heavy-
tailed noise. This setting with deep neural networks is studied in [57].

We introduce a generic loss function, which satisfies the following
assumption:

######  Assumption 4.

A loss function $\ell:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$ is symmetric
and $\ell(x,y)$ is Lipschitz-continuous in each $x$ and $y$ with its Lipschitz
constant $C_{\ell}>0$. Further, $\ell(y,x)=0$ holds if and only if $y=x$, and
there exists a constant $c_{\ell}>0$ and $q\geq 1$ such that

$\displaystyle\ell(y,x)\geq c_{\ell}|y-x|^{q},\forall x,y\in\mathbb{R}.$ (34)

A class of loss function satisfying Assumption 4 includes several
representative loss functions, e.g., an absolute loss $\ell(y,x)=|y-x|$, a
quantile loss $\ell(y,x)=(\textbf{1}\\{y\geq x\\}\tau+\textbf{1}\\{y\leq
x\\}(\tau-1))(y-x)$ for $\tau\in(0,1)$, and the Cauchy loss
$\ell(y,x)=\log(1+\kappa^{2}(y-x)^{2})$ for $\kappa>0$.

We introduce an empirical risk function for adversarial training based on
$\ell$. Using the neighbourhood set $\Delta_{h}^{p}(x)$ and the preprocessing
$\widehat{Y}$, we define an empirical risk function as

$\displaystyle\widetilde{R}_{n}(f):=\frac{1}{n}\sum_{i=1}^{n}\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}\ell(\widehat{Y}(x^{\prime}),f(x^{\prime})).$
(35)

This loss function is a generalized version of the ordinary loss for the
adversarial training (19). Using this notion, we define its minimizer as

$\displaystyle\widetilde{f}\in\operatornamewithlimits{argmin}_{f\in\mathcal{F}(L,W)}\widetilde{R}_{n}(f).$
(36)

####  5.1.2. Error Analysis

We study an $L^{\infty}$-risk of this estimator by deriving a non-asymptotic
upper bound. The proof differs from that of Theorem 3, requiring a more
general treatment of loss combined with adversarial training.

######  Proposition 6.

Consider the regression model (1) and the adversarial estimator
$\widetilde{f}$ in (36) with the function class by deep neural networks with a
tuple $(L,W)$ and $h\in(0,1)$. Suppose Assumption 1 and 2 for $\beta>0$,
Assumption 3 holds with
$\zeta_{n}^{2}=O(n^{-2\beta/(2\beta+d)}\log^{\beta^{*}}n)$ for some
$\beta^{*}>0$ and $\widehat{Y}$ is independent of
$\\{(X_{i},Y_{i})_{i=1}^{n}\\}$, and Assumption 4 holds with $q\in[1,\infty)$.
Then, we have the following as $n\to\infty$:

$\displaystyle\mathbb{E}\left[\|\widetilde{f}-f^{*}\|_{L^{\infty}}^{2}\right]=O\left(h^{-2d/q}n^{-\beta/(q(\beta+d))}\log^{(2/q)\vee\beta^{*}}n\right).$
(37)

This result shows that the $L^{\infty}$-risk is bounded with the setup with
general loss functions. The convergence rate of Proposition 6 of the
$L^{\infty}$-risk corresponds to a convergence rate of excess risks derived by
Theorem 4.2 in [57] under general losses. The key to this result is the bound
$V$ on $\mathbb{E}[\|\widehat{Y}\|_{L^{\infty}}^{2}]$ given in Assumption 3.
The independence of the preprocessing $\widehat{Y}$ is imposed because of a
technical reason, however, it is easy to satisfy it. For example, we can
randomly split the observed data into two and then conduct the preprocessing
using one of the two.

The technical derivation is similar to that of Theorem 3. First, we define an
expected value of adversarial risk with the general loss and the
preprocessing: for $f\in\mathcal{F}(L,W)$, we define

$\displaystyle\tilde{R}(f):=\mathbb{E}_{X}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}\ell(f(x^{\prime}),\widehat{Y}(x^{\prime}))\right].$
(38)

Then, we derive an upper bound for an excess value of the risk
$\widetilde{R}(\widetilde{f})-\widetilde{R}(f^{*})$ in Proposition 6. Next, we
bound the $L^{\infty}$-risk by properties of the expected adversarial risk as

$\displaystyle\|\widetilde{f}-f^{*}\|_{L^{\infty}}^{q}=O\left(h^{-d}\left(\widetilde{R}(\widetilde{f})-\widetilde{R}(f^{*})+\|\widehat{Y}-f^{*}\|_{L^{\infty}}\right)\right).$
(39)

in Lemma 14. This result is an extension of the bound for the
$L^{\infty}$-risk by the $L^{2}$-risk as shown in Lemma 5. Combining the
results, we obtain the result of Proposition 6.

###  5.2. Adaptation to Heterogeneous Smoothness with Besov Space

####  5.2.1. Motivation and Setting

In this section, we show that our proposed method can be adapted to estimate
functions with heterogeneous smoothness, that is, we study the case that the
true function $f^{*}$ is an element of the Besov space (see [17] for an
introduction). The Besov space has an interesting property that linear
estimators, a certain type of non-deep estimators, cannot estimate its
elements with the optimal convergence rate.

First, we give the definition of the Besov space following [35, 17]. Note that
there are several equivalent definitions for Besov spaces, and the following
is based on the notion of difference of functions. Consider parameters
$p,q\in(0,\infty]$ and $\beta>0$. For $r\in\mathbb{N}$, $h\in\mathbb{R}^{d}$,
and $f:[0,1]^{d}\to\mathbb{R}$, we define an $r$-th difference of $f$ at
$x\in[0,1]^{d}$ as

$\displaystyle\Delta_{h}^{r}[f](x)=\textbf{1}\\{x+rh\in[0,1]^{d}\\}\sum_{j=1}^{r}\binom{r}{j}(-1)^{r-j}f(x+jh).$
(40)

We also define the $r$-th modulus of smoothness of $f$ with $u>0$ as

$\displaystyle\omega_{r,p}(f,u)=\sup_{\|h\|_{2}\leq
u}\|\Delta_{h}^{r}[f]\|_{L^{p}(\lambda)}.$ (41)

Recall that $\|\cdot\|_{L^{p}(\lambda)}$ denotes the $L^{p}$-norm with the
Lebesgue measure $\lambda$. Using these notions, we define a ball in the Besov
space as follows. .

######  Definition 1 (Besov space).

With $r\in\mathbb{N}$ such that define $r>\beta$, we define a semi-norm of
$f:[0,1]^{d}\to\mathbb{R}$ as

$\displaystyle\|f\|_{\mathcal{B}_{p,q}^{\beta}}:=\begin{cases}\int_{0}^{\infty}((u^{-\beta}\omega_{r,p}(f,u))^{q}u^{-1}du)^{1/q}&\mbox{~{}if~{}}q<\infty\\\
\sup_{u>0}u^{-\beta}\omega_{r,p}(f,u)&\mbox{~{}if~{}}q=\infty.\end{cases}$
(42)

Then, we define a ball of the Besov space with its radius $B\geq 1$ as

$\displaystyle\mathcal{B}_{p,q}^{\beta}:=\left\\{f:[0,1]^{d}\to\mathbb{R}\mid\|f\|_{L^{p}(\lambda)}+\|f\|_{\mathcal{B}_{p,q}^{\beta}}\leq
B\right\\}.$ (43)

The Besov space can represent functions with discontinuity and heterogeneous
smoothness, which means that the degree of smoothness of functions varies
depending on $x$. These properties follow the fact that
$\mathcal{B}_{1,1}^{1}$ coincides with the space of bounded total variation
[47].

An important property of heterogeneous smoothness is that deep estimators,
such as deep neural networks, tend to have an advantage in estimating such
functions. Specifically, a linear estimator, which is one certain family of
non-deep estimators [34], becomes sub-optimal when estimating elements of the
Besov space. The linear estimator has a form
$\widehat{f}^{\mathrm{lin}}(\cdot)=\sum_{i=1}^{n}\Psi(\cdot;X_{1},...,X_{n})Y_{i}$
with an arbitrary measurable map $\Psi$, and includes major estimators such as
the kernel ridge estimator. Then, Theorem 1 in [75] implies the following
minimax lower bound with $d=1$ case:

$\displaystyle\min_{\widehat{f}^{\mathrm{lin}}}\max_{f^{*}\in\mathcal{B}_{p,q}^{\beta}}\mathbb{E}\left[\|\widehat{f}^{\mathrm{lin}}-f^{*}\|_{L^{2}(\lambda)}^{2}\right]\geq
Cn^{-2\beta^{\prime}/(2\beta^{\prime}+d)},$ (44)

with some $C>0$ and $\beta^{\prime}=\beta+1/2-1/p$. For $p<2$ case, the linear
estimator is sub-optimal, hence the rate is slower than the minimax optimal
rate $\widetilde{O}(n^{-2\beta/(2\beta+d)})$. Several studies [10, 63, 58]
show similar statements. Therefore, it is important to estimate functions in
the Besov space with deep neural networks, since it overcomes the limitations
of linear estimators.

####  5.2.2. Error Analysis

We give a convergence rate of the adversarial estimator with deep neural
networks and the preprocessing in (20). Note that we consider the adversarial
risk (19) based on the squared loss function. We first give the following
assumption.

######  Assumption 5.

There exists $\beta>0$ such that $f^{*}\in\mathcal{B}_{p,q}^{\beta^{\prime}}$
holds for every $\beta^{\prime}\in(0,\beta]$.

To estimate functions in the Besov space, we have to restrict a set of neural
network functions. Let $\overline{\mathcal{F}}(L,W,S,\bar{B})$ be a set of
neural network functions (14) such that there are $S\in\mathbb{N}$ non-zero
parameters and each value is included in $[-\bar{B},\bar{B}]$ with
$\bar{B}\geq 1$, then consider the empirical preprocessed adversarial risk
(19) on $\overline{\mathcal{F}}(L,W,S,\bar{B})$ as

$\displaystyle\widehat{f}\in\operatornamewithlimits{argmin}_{f\in\overline{\mathcal{F}}(L,W,S,\bar{B})}R_{n}(f).$
(45)

Then, we give the convergence rate of the estimator, which corresponds to the
minimax optimal rate $\widetilde{O}(n^{-2\beta/(2\beta+d)})$ [17]. Note that
this rate is valid regardless of the values of $p$ and $q$.

######  Proposition 7.

Fix $p,q\in(0,\infty]$. Consider the regression model (1) and the adversarial
estimator $\widehat{f}$ in (45) with the function class
$\overline{\mathcal{F}}(L,W,S,\bar{B})$ by deep neural networks. Suppose that
Assumption 1, and 5 hold with $\beta>d/p$. Further, suppose that
$\zeta_{n}^{2}=O(n^{-2\beta/(2\beta+d)}\log^{\beta^{*}}n)$ for some
$\beta^{*}>0$. We set $L$ and $W$ as $L\geq C_{d,p,\beta,B}\log n$, $S\asymp
W\asymp n^{d/(2\beta+d)}$, and $\bar{B}=O(n^{a})$ with some $a>0$. Then, we
obtain the following as $n\to\infty$:

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]=O\left(n^{-2\beta/(2\beta+d)}\log^{3\vee\beta^{*}}n\right).$
(46)

The result shows that our estimator with deep neural networks inherits the
advantages of both deep and non-deep estimators. Rigorously, first, it
achieves the minimax optimal rate up to log factors. This optimality is not
achieved by the linear estimator and is one of the advantages of using deep
neural networks. Next, the errors are convergent in the sup-norm sense. This
is not shown by deep neural network estimators using the least squares, and is
achieved by adversarial training with preprocessing. Note that the requirement
on the preprocessing is satisfied by, for example, the wavelet estimator with
$\beta^{*}=2\beta/(2\beta+d)$ [40, 17].

The proof of this proposition is a slight modification of the proof of
Proposition 8 in Appendix. The main update is an analysis of the approximation
error by deep neural networks to a function in the Besov space. Here, we apply
the seminal result by [63] on the approximation error in the sup-norm.

##  6\. Simulations

In this section, we conduct simulation experiments to justify the theoretical
results. Specifically, we generate data from a function and then numerically
compute the $L^{\infty}$-risk of the proposed estimator and other standard
methods.

We generate $n$ samples from the regression model (1) with the sample size
$n\in\\{400,800,1200,1600\\}$ and the noise variance
$\sigma^{2}\in\\{0.0001,0.01,1.0\\}$. We consider the following three cases as
values of $f^{*}$ on $[0,1]^{d}$. In Case 1, we set $d=1$ and
$f^{*}(x)=0.3\sin(4\pi x)-x+0.5$. In Case 2, we set $d=2$ and
$f^{*}(x_{1},x_{2})=\sin(4\pi x_{1})+\cos(2\pi x_{2})$. In Case 3, we set
$d=7$ and
$f^{*}(x_{1},x_{2},...,x_{7})=\frac{2}{x_{1}+0.01}+3\log(x_{2}^{7}x_{3}+0.1)x_{4}+0.1x_{5}^{4}x_{6}^{2}x_{7}$.

For estimation, we use a three-layer fully-connected neural network with the
ReLU activation function. The width of each layer is $40$. For training, we
use three methods: (i) adversarial training without preprocessing, (ii)
adversarial training with preprocessing (our proposal), and (iii) ordinary
least squares. In the adversarial training case (i) and (ii), the value of $h$
is set to $2^{-3}$. For the adversarial training, we employ the projected
descent algorithm [43]. For the preprocessing, we employ the $k$-nearest
neighbor with setting $k=3$. To measure the $L^{\infty}$-risk, we generate
$10,000$ uniform random variables on the support $[0,1]^{d}$ and use their
maximum to approximate the risk.

Figure 3 shows the measured $L^{\infty}$-risk against the sample size $n$. We
have mainly three findings: (i) In approximately all cases, our proposed
estimator from adversarial training with preprocessing monotonically reduces
the $L^{\infty}$-risk in $n$. (ii) The adversarial estimators without
preprocessing may or may not be as good as those with preprocessing. This
implies that the magnitude of the bias from adversarial training depends on
the shape of the true function $f^{*}$. (iii) The $L^{\infty}$-risk of the
least square estimator generally decreases at a slower rate or does not
decrease in all cases. This supports the possibility that training a deep
neural network with least-squares may have difficulty in reducing the
$L^{\infty}$-risk.

Figure 3. $L^{\infty}$-risk against the sample size $n$. The mean and standard
deviation of the 10 repetitions are plotted.

##  7\. Conclusion and Discussion

We consider the nonparametric function estimator by deep neural networks that
converge in the sense of the sup-norm, i.e., $L^{\infty}$-norm. Since deep
neural networks do not have a tractable structure such as a linear sum of
basis functions as the conventional non-deep estimators, they are not
guaranteed to converge in the sup-norm sense. In this study, we tackle this
problem by considering the estimator based on adversarial training. For the
bias due to the adversarial training, we solve this problem by introducing the
preprocessing for the data. As a result, our proposed corrected adversarial
converges to the smooth true function with the minimax optimal rate in the
sup-norm sense. Our approach is also valid for functions with general loss and
functions with heterogeneous smoothness. The experiments support our
theoretical results.

Future research directions include sup-norm convergence for estimating non-
smooth functions. Although we expect that there are significant obstacles to
the sup-norm convergence of estimators for the non-smooth functions, it is
interesting to argue how far we can relax the conditions to estimate such
functions. Another direction is the application of uniform confidence bands
for functions. Our sup-norm convergence is useful to study the uncertainty of
neural network estimators and constructing uniform confidence bands. These
directions may be a step toward statistical inference with deep neural
networks.

##  Appendix A Proof for Main Result in Section 4

###  A.1. Overview

We first develop a general theorem with arbitrary preprocessing, then apply
the result and prove the results in Section 4. For a preprocessed output
$\widehat{Y}$, we define its residual as

$\displaystyle\Xi(x):=\widehat{Y}(x)-f^{*}(x),~{}x\in[0,1]^{d}.$ (47)

This notion expresses an error in estimating the true function $f^{*}$ by the
preprocessing $\widehat{Y}$.

######  Proposition 8.

Consider the regression model (1) and the corrected adversarial estimator
$\widehat{f}$ as (20) with the function class $\mathcal{F}(L,W)$ by deep
neural networks. Suppose that Assumption 2 and 1 hold. Then, we obtain

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]$
(48) $\displaystyle\leq
C_{P_{X},p,d,B}h^{-d}\left(\frac{W^{2}L^{2}\log(WL)\log
n}{n}+\Phi_{L,W}^{2}+\mathbb{E}[\|\Xi\|_{L^{\infty}}]\Phi_{L,W}+h^{-d}\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]\right).$
(49)

###### Proof of Proposition 8.

We apply Lemma 9 to bound the sup-norm as

$\displaystyle\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\leq
2(C_{P_{X},p,d}h^{d})^{-1}\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}$ (50)

Note that any $f\in\mathcal{F}(L,W)$ is continuous, since it has a form of
deep neural network with the ReLU activation with continuity. We then take an
expectation of the bounds and apply Lemma 10 and Proposition 12 to obtain

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\right]$
(51) $\displaystyle\leq
4\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{n,\Delta}^{2}\right]+\frac{800B^{2}\log
N_{L,W}(\delta)+4118B^{2}}{n}+32\delta B+8\delta^{2}$ (52)
$\displaystyle\leq\left(16\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]^{1/2}+40\delta\right)\left(\frac{\log
N_{L,W}(\delta)}{n}+\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]\right)^{1/2}$
(53) $\displaystyle\quad+\frac{800B^{2}\log
N_{L,W}(\delta)+4118B^{2}}{n}+32\delta
B+8\delta^{2}+4\Phi_{L,W}^{2}+8\mathbb{E}[\|\Xi\|_{L^{\infty}}]\Phi_{L,W}+2\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right],$
(54)

for $\delta\in(0,1]$. Note that both $f\in\mathcal{F}(L,W)$ and $f^{*}$ are
bounded, the expectations are guaranteed to exist. We combine this fact with
the above inequality to (50), then obtain

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]$
(55) $\displaystyle\leq
C_{P_{X},p,d}h^{-d}\left(\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]^{1/2}+\delta\right)\left(\frac{\log
N_{L,W}(\delta)}{n}+\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]\right)^{1/2}$
(56) $\displaystyle\quad+C_{P_{X},p,d}h^{-d}\left(\frac{B^{2}\log
N_{L,W}(\delta)+B^{2}}{n}+\delta
B+\Phi_{L,W}^{2}+\mathbb{E}[\|\Xi\|_{L^{\infty}}]\Phi_{L,W}+\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]\right),$
(57)

by setting $\delta\leq B\vee\Phi_{L,W}$, which will be verified later.

We arrange the terms in the above inequality. For $a,b\geq 0$ and
$z\in\mathbb{R}$, $z^{2}\leq az+b$ implies $z^{2}\leq 3a^{2}+2b$. with
regarding regard $z=\mathbb{E}[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}]^{1/2}$
and obtain

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]$
(58) $\displaystyle\leq C_{P_{X},p,d,B}h^{-d}\Biggl{\\{}\frac{\log
N_{L,W}(\delta)}{n}+\delta+\Phi_{L,W}^{2}+\mathbb{E}[\|\Xi\|_{L^{\infty}}]\Phi_{L,W}+h^{-d}\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]$
(59) $\displaystyle\qquad\qquad\qquad\qquad+\left(\frac{\log
N_{L,W}(\delta)}{n}+\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]\right)^{1/2}\delta\Biggr{\\}}.$
(60)

Further, we set $\delta=1/n$ then Lemma 16 shows

$\displaystyle\log
N_{L,W}(1/n)=\log\sup_{Q_{n}}N(1/n,\mathcal{F}(L,W),\|\cdot\|_{L^{2}(Q_{n})})\leq
CW^{2}L^{2}\log(WL)\log(Bn^{2}).$ (61)

We substitute these results and obtain the statement.

∎

######  Lemma 9.

Suppose $P_{X}$ satisfies Assumption 1 and $f^{*}$ is continuous. For any
bounded and continuous $f:[0,1]^{d}\to\mathbb{R}$, we have

$\displaystyle\|{f}-f^{*}\|_{P_{X},\Delta}^{2}\geq
C_{P_{X},p,d}h^{d}\|{f}-f^{*}\|_{L^{\infty}}^{2}.$ (62)

###### Proof of Lemma 9.

We apply Lemma 15 to achieve the statement. To apply the lemma, we verify that
the map $x^{\prime}\mapsto({f}(x^{\prime})-f^{*}(x^{\prime}))^{2}$ is bounded
and continuous by the compactness of the domain $[0,1]^{d}$ and the
assumptions. Then, we have

$\displaystyle\|{f}-f^{*}\|_{P_{X},\Delta}^{2}\geq
C_{P_{X},p,d}h^{d}\sup_{x^{\prime}\in[0,1]^{d}}({f}(x^{\prime})-f^{*}(x^{\prime}))^{2}=C_{P_{X},p,d}h^{d}\|{f}-f^{*}\|_{L^{\infty}}^{2}.$
(63)

The inequality follows Lemma 15 by setting
$g(\cdot)=({f}(\cdot)-f^{*}(\cdot))^{2}$. ∎

######  Lemma 10.

All $f\in\mathcal{F}$ is continuous. Suppose that $f^{*}$ is continuous and
$\|f^{*}\|_{L^{\infty}}\leq B$ holds. Then, for any $\delta>0$, we have

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\right]$
(64) $\displaystyle\leq
4\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{n,\Delta}^{2}\right]+\frac{800B^{2}\log
N_{L,W}(\delta)+4118B^{2}}{n}+32\delta B+8\delta^{2}.$ (65)

###### Proof of Lemma 10.

Without loss of generality, we assume that $N_{L,W}(\delta)\geq 3$ and $\log
N_{L,W}(\delta)\leq n$. Also, we define the nearest element of the covering
set to $\widehat{f}$, that is, we define
$\widehat{j}:=\operatornamewithlimits{argmin}_{j^{\prime}=1,...,N}\sup_{Q_{n}}\|f_{j^{\prime}}-\widehat{f}\|_{L^{2}(Q_{n})}$.
Let $X_{i}^{\prime}$ be an i.i.d. samples from $P_{X}$ for $i=1,...,n$. Note
that $\widehat{Y}$ depends on $X_{1},...,X_{n}$.

We give a bound on the following difference as

$\displaystyle\left|\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\right]-\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{n,\Delta}^{2}\right]\right|$
$\displaystyle=\left|\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i}^{\prime})}(\widehat{f}(x^{\prime})-f^{*}(x^{\prime}))^{2}-\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}(\widehat{f}(x^{\prime})-f^{*}(x^{\prime}))^{2}\right]\right|$
$\displaystyle\leq\Biggl{|}\mathbb{E}\Biggl{[}\frac{1}{n}\sum_{i=1}^{n}\underbrace{\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i}^{\prime})}({f}_{\widehat{j}}(x^{\prime})-f^{*}(x^{\prime}))^{2}-\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}({f}_{\widehat{j}}(x^{\prime})-f^{*}(x^{\prime}))^{2}}_{=:g_{\widehat{j}}(X_{i},X_{i}^{\prime})}\Biggr{]}\Biggr{|}$
$\displaystyle\quad+2\left|\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}(\widehat{f}(x^{\prime})-{f}_{\widehat{j}}(x^{\prime})+{f}_{\widehat{j}}(x^{\prime})-f^{*}(x^{\prime}))^{2}-\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}({f}_{\widehat{j}}(x^{\prime})-f^{*}(x^{\prime}))^{2}\right]\right|$
$\displaystyle\leq\Biggl{|}\mathbb{E}\Biggl{[}\frac{1}{n}\sum_{i=1}^{n}g_{\widehat{j}}(X_{i},X_{i}^{\prime})\Biggr{]}\Biggr{|}+4\mathbb{E}\left[\sup_{Q_{n}}\|\widehat{f}-{f}_{\widehat{j}}\|_{L^{2}(Q_{n})}^{2}\right]^{1/2}\mathbb{E}\left[\sup_{Q_{n}}\|{f}_{\widehat{j}}-f^{*}\|_{L^{2}(Q_{n})}^{2}\right]^{1/2}$
$\displaystyle\quad+2\mathbb{E}\left[\sup_{Q_{n}}\|\widehat{f}-{f}_{\widehat{j}}\|_{L^{2}(Q_{n})}^{2}\right]$
$\displaystyle\leq\Biggl{|}\mathbb{E}\Biggl{[}\frac{1}{n}\sum_{i=1}^{n}g_{\widehat{j}}(X_{i},X_{i}^{\prime})\Biggr{]}\Biggr{|}+4\delta\mathbb{E}\left[\|{f}_{\widehat{j}}-f^{*}\|_{L^{\infty}}^{2}\right]^{1/2}+2\delta^{2}$
$\displaystyle\leq\Biggl{|}\mathbb{E}\Biggl{[}\frac{1}{n}\sum_{i=1}^{n}g_{\widehat{j}}(X_{i},X_{i}^{\prime})\Biggr{]}\Biggr{|}+8\delta
B+2\delta^{2}.$ (66)

Here, the second last inequality follows Lemma 17 using the continuity of
$f^{*}$ and the $f\in\mathcal{F}$. The last inequality follows the definition
of $\widehat{j}$ and the boundedness of $f\in\mathcal{F}$ and $f^{*}$ by $B$.

We further study the first term of the bound (66). As preparation, we define

$\displaystyle
r_{j}=B\max\left\\{\mathbb{E}\left[\|f_{j}-f^{*}\|_{P_{X},\Delta}^{2}\right]^{1/2},(n^{-1}\log
N_{L,W}(\delta))^{1/2}\right\\},$ (67)

for $j=1,...,N$, and it yields

$\displaystyle r_{\widehat{j}}$ $\displaystyle\leq B\mathbb{E}_{X\mid
X_{1:n},Y_{1:n}}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}(f_{\widehat{j}}(x^{\prime})-f^{*}(x^{\prime}))^{2}\right]^{1/2}+B(n^{-1}\log
N_{L,W}(\delta))^{1/2}$ $\displaystyle\leq B\mathbb{E}_{X\mid
X_{1:n},Y_{1:n}}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}(\widehat{f}(x^{\prime})-f^{*}(x^{\prime}))^{2}\right]^{1/2}+B(n^{-1}\log
N_{L,W}(\delta))^{1/2}+B\delta.$ (68)

Here, $\mathbb{E}_{X\mid X_{1:n},Y_{1:n}}[\cdot]$ denotes a conditional
expectation with given $X_{1},...,X_{n}$ and $Y_{1},...,Y_{n}$. By the law of
iterated expectation, the first term of the bound is decomposed as

$\displaystyle\Biggl{|}\mathbb{E}\Biggl{[}\frac{1}{n}\sum_{i=1}^{n}g_{\widehat{j}}(X_{i},X_{i}^{\prime})\Biggr{]}\Biggr{|}$
$\displaystyle=\frac{1}{n}\Biggl{|}\mathbb{E}\Biggl{[}\sum_{i=1}^{n}\underbrace{\frac{g_{\widehat{j}}(X_{i},X_{i}^{\prime})}{r_{\widehat{j}}}}_{=:\widetilde{g}_{\widehat{j}}(X_{i},X_{i}^{\prime})}r_{\widehat{j}}\Biggr{]}\Biggr{|}$
$\displaystyle\leq\frac{1}{n}\Biggl{|}\mathbb{E}\Biggl{[}\sum_{i=1}^{n}\widetilde{g}_{\widehat{j}}(X_{i},X_{i}^{\prime})\left(B\mathbb{E}_{X\mid
X_{1:n},Y_{1:n}}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}(\widehat{f}(x^{\prime})-f^{*}(x^{\prime}))^{2}\right]^{1/2}+B(n^{-1}\log
N_{L,W}(\delta))^{1/2}+B\delta\right)\Biggr{]}\Biggr{|}$
$\displaystyle\leq\frac{1}{n}\Biggl{|}\mathbb{E}\Biggl{[}\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\left(B\mathbb{E}_{X\mid
X_{1:n},Y_{1:n}}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}(\widehat{f}(x^{\prime})-f^{*}(x^{\prime}))^{2}\right]^{1/2}\right)\Biggr{]}\Biggr{|}$
$\displaystyle\quad+\frac{B}{n}\Biggl{|}\mathbb{E}\Biggl{[}\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\left((n^{-1}\log
N_{L,W}(\delta))^{1/2}+\delta\right)\Biggr{]}^{1/2}\Biggr{|}$
$\displaystyle\leq\frac{B}{n}\Biggl{|}\mathbb{E}\Biggl{[}\left(\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\right)^{2}\Biggr{]}^{1/2}\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\right]^{1/2}\Biggr{|}$
$\displaystyle\quad+\frac{B}{n}\mathbb{E}\Biggl{[}\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\Biggr{]}\left((n^{-1}\log
N_{L,W}(\delta))^{1/2}+\delta\right)$ $\displaystyle\leq\frac{B}{n}(36n\log
N_{L,W}(\delta)+256n)^{1/2}\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\right]^{1/2}+\frac{B}{n}(6\log
N_{L,W}(\delta)+11).$ (69)

The first inequality follows (68) and the second last inequality follows the
Cauchy-Schwartz inequality. We also apply Lemma 11 and $1\leq\log
N_{L,W}(\delta)\leq n$ to achieve the last inequality.

We substitute the result (69) into the bound (66), then obtain the inequality:

$\displaystyle\left|\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\right]-\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{n,\Delta}^{2}\right]\right|$
(70) $\displaystyle\leq\frac{B}{n}(36n\log
N_{L,W}(\delta)+256n)^{1/2}\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\right]^{1/2}+\frac{B}{n}(6\log
N_{L,W}(\delta)+11)+8\delta B+2\delta^{2}.$ (71)

We rearrange the term and obtain that

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{P_{X},\Delta}^{2}\right]$
(72) $\displaystyle\leq
2\left(\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{n,\Delta}^{2}\right]+\frac{B}{n}(6\log
N_{L,W}(\delta)+11)+8\delta B+2\delta^{2}\right)+\frac{8B^{2}(36n\log
N_{L,W}(\delta)+256n)}{n^{2}}.$ (73)

Then, we obtain the statement. ∎

######  Lemma 11.

Suppose that $N_{L,W}(\delta)\geq 3$. For the function
$\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})$ defined in the proof of Lemma 10,
we have

$\displaystyle\mathbb{E}\Biggl{[}\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\Biggr{]}\leq
6(n\log N_{L,W}(\delta))^{1/2}+\frac{32n^{1/2}}{3(\log
N_{L,W}(\delta))^{1/2}},$ (74)

and

$\displaystyle\mathbb{E}\Biggl{[}\left(\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\right)^{2}\Biggr{]}\leq
36n\log N_{L,W}(\delta)+256n.$ (75)

###### Proof of Lemma 11.

We first note that for any $j=1,...,N_{L,W}(\delta)$, we have
$\mathbb{E}[\widetilde{g}_{j}(X_{i},X_{i}^{\prime})]=0$,
$|\widetilde{g}_{j}(X_{i},X_{i}^{\prime})|\leq 4B^{2}/r_{j}\leq 4n^{1/2}/(\log
N_{L,W}(\delta))^{1/2}=:M$, and

$\displaystyle\operatorname{Var}(\widetilde{g}_{j}(X_{i},X_{i}^{\prime}))$
$\displaystyle=2r_{j}^{-2}\operatorname{Var}\left(\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{1})}(f_{j}(x^{\prime})-f^{*}(x^{\prime}))^{2}\right)$
(76) $\displaystyle\leq
2r_{j}^{-2}\mathbb{E}\left[\left(\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{1})}(f_{j}(x^{\prime})-f^{*}(x^{\prime}))^{2}\right)^{2}\right]$
(77) $\displaystyle\leq
8r_{j}^{-2}\mathbb{E}\left[\|f_{j}-f^{*}\|_{P_{X},\Delta}^{2}\right]B^{2}$
(78) $\displaystyle\leq 8.$ (79)

The second inequality follows Hölder’s inequality. Using the bounds above, we
apply the Bernstein inequality as

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\geq
t\right)$
$\displaystyle\leq\exp\left(-\frac{t^{2}}{2tM/3+2n\operatorname{Var}(\widetilde{g}_{j}(X_{1},X_{1}^{\prime}))}\right)$
$\displaystyle\leq\exp\left(-\frac{t^{2}}{8tn^{1/2}(\log
N_{L,W}(\delta))^{-1/2}/3+16n}\right)$
$\displaystyle\leq\exp\left(-\frac{t^{2}}{16tn^{1/2}(\log
N_{L,W}(\delta))^{-1/2}/3}\right)$ $\displaystyle=\exp\left(-\frac{3t(\log
N_{L,W}(\delta))^{1/2}}{16n^{1/2}}\right),$ (80)

for $t\geq 6(n\log N_{L,W}(\delta))^{1/2}$. The last inequality follows
$8tn^{1/2}(\log N_{L,W}(\delta))^{-1/2}/3\geq 16n$ for $t$ larger than the
threshold $6(n\log N)^{1/2}$.

Using the result (80) associated with $t\geq 6(n\log N_{L,W}(\delta))^{1/2}$,
we bound the following expectation:

$\displaystyle\mathbb{E}\Biggl{[}\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\Biggr{]}$
(81)
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\left(\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\geq
t\right)dt$ (82) $\displaystyle\leq 6(n\log
N_{L,W}(\delta))^{1/2}+2N_{L,W}(\delta)\int_{6(n\log
N_{L,W}(\delta))^{1/2}}^{\infty}\max_{j=1,...,N_{L,W}(\delta)}\mathbb{P}\left(\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\geq
t\right)dt$ (83) $\displaystyle\leq 6(n\log
N_{L,W}(\delta))^{1/2}+2N_{L,W}(\delta)\int_{6(n\log
N_{L,W}(\delta))^{1/2}}^{\infty}\exp\left(-\frac{3t(\log
N_{L,W}(\delta))^{1/2}}{16n^{1/2}}\right)dt$ (84) $\displaystyle\leq 6(n\log
N_{L,W}(\delta))^{1/2}+\frac{32n^{1/2}}{3(\log N_{L,W}(\delta))^{1/2}}.$ (85)

Then, the first statement is proved.

For the second statement, we similarly apply (80) and obtain Using the result
(80) associated with $t\geq 6(n\log N_{L,W}(\delta))^{1/2}$, we bound the
following expectation:

$\displaystyle\mathbb{E}\Biggl{[}\left(\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\right)^{2}\Biggr{]}$
(86)
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\left(\max_{j=1,...,N_{L,W}(\delta)}\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\geq
t^{1/2}\right)dt$ (87) $\displaystyle\leq 36n\log
N_{L,W}(\delta)+2N_{L,W}(\delta)\int_{6n\log
N_{L,W}(\delta)}^{\infty}\max_{j=1,...,N_{L,W}(\delta)}\mathbb{P}\left(\sum_{i=1}^{n}\widetilde{g}_{{j}}(X_{i},X_{i}^{\prime})\geq
t^{1/2}\right)dt$ (88) $\displaystyle\leq 36n\log
N_{L,W}(\delta)+2N_{L,W}(\delta)\int_{6n\log
N_{L,W}(\delta)}^{\infty}\exp\left(-\frac{3t^{1/2}(\log
N_{L,W}(\delta))^{1/2}}{16n^{1/2}}\right)dt$ (89) $\displaystyle\leq 36n\log
N_{L,W}(\delta)+256n.$ (90)

Then, the second statement is also proved. ∎

######  Proposition 12.

Consider the setting in Theorem 3. Then, for any $\delta\in(0,1]$, we have

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{n,\Delta}^{2}\right]$
$\displaystyle\leq\left(4\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]^{1/2}+10\delta\right)\left(\frac{\log
N_{L,W}(\delta)}{n}+\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]\right)^{1/2}$
(91)
$\displaystyle\quad+\Phi_{L,W}^{2}+2\mathbb{E}[\|\Xi\|_{L^{\infty}}]\Phi_{L,W}+2\mathbb{E}[\|\Xi\|_{L^{\infty}}^{2}].$
(92)

###### Proof of Proposition 12.

By the definition of the minimization problem,
${L}_{n}(\widehat{f})\leq{L}_{n}(f)$ holds for any $f\in\mathcal{F}(L,W)$,
hence we have the following basic inequality as

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}(\widehat{Y}(x^{\prime})-\widehat{f}(x^{\prime}))^{2}\leq\frac{1}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}(\widehat{Y}(x^{\prime})-f(x^{\prime}))^{2},$
(93)

which can be rewritten as

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}(f^{*}(x^{\prime})+\Xi(x^{\prime})-\widehat{f}(x^{\prime}))^{2}\leq\frac{1}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}(f^{*}(x^{\prime})+\Xi(x^{\prime})-f(x^{\prime}))^{2}.$
(94)

We bound the both-hand side of (94). The left-hand side (LHS) of (94) is lower
bounded as

LHS of (94)
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}\left\\{(f^{*}(x^{\prime})-\widehat{f}(x^{\prime}))^{2}+\Xi(x^{\prime})^{2}+2\Xi(x^{\prime})(f^{*}(x^{\prime})-\widehat{f}(x^{\prime}))\right\\}$
$\displaystyle\geq\|f^{*}-\widehat{f}\|_{n,\Delta}^{2}-\|\Xi\|_{n,\Delta}^{2}-\frac{2}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}|\Xi(x^{\prime})(f^{*}(x^{\prime})-\widehat{f}(x^{\prime}))|,$
(95)

by applying Lemma 18. Similarly, we bound the right-hand side of (94) as

RHS of (94)
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}\left\\{(f^{*}(x^{\prime})-{f}(x^{\prime}))^{2}+\Xi(x^{\prime})^{2}+2\Xi(x^{\prime})(f^{*}(x^{\prime})-{f}(x^{\prime}))\right\\}$
$\displaystyle\leq\|f^{*}-{f}\|_{n,\Delta}^{2}+\|\Xi\|_{n,\Delta}^{2}+\frac{2}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}|\Xi(x^{\prime})(f^{*}(x^{\prime})-{f}(x^{\prime}))|.$
(96)

Combining (95) and (96) with (94), we obtain

$\displaystyle\|f^{*}-\widehat{f}\|_{n,\Delta}^{2}$
$\displaystyle\leq\|f^{*}-{f}\|_{n,\Delta}^{2}+2\|\Xi\|_{n,\Delta}^{2}+\underbrace{\frac{2}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}|\Xi(x^{\prime})(f^{*}(x^{\prime})-\widehat{f}(x^{\prime}))|}_{=:T_{1}}$
$\displaystyle\quad+\frac{2}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}|\Xi(x^{\prime})(f^{*}(x^{\prime})-{f}(x^{\prime}))|$
$\displaystyle\leq\Phi_{L,W}^{2}+2\|\Xi\|_{L^{\infty}}^{2}+T_{1}+2\|\Xi\|_{L^{\infty}}\Phi_{L,W},$
(97)

by the definition of $\Phi_{L,W}$ in (29). We will bound an expectation the
terms. Note that the expectations of the terms are guaranteed to exist, by the
boundedness of $f^{*}$ and $\widehat{f},f\in\mathcal{F}(L,W)$, and
$\widehat{Y}$.

We bound $\mathbb{E}[T_{1}]$. We define the nearest element of the covering
set to $\widehat{f}$, that is, we define
$\widehat{j}:=\operatornamewithlimits{argmin}_{j^{\prime}=1,...,N}\sup_{Q_{n}}\|f_{j^{\prime}}-\widehat{f}\|_{L^{2}(Q_{n})}$.
Then, we bound $\mathbb{E}[T_{1}]$ as

$\displaystyle\mathbb{E}[T_{1}]$
$\displaystyle=\mathbb{E}\left[\frac{2}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}(X_{i})}|\Xi(x^{\prime})(f^{*}(x^{\prime})-f_{\widehat{j}}(x^{\prime})+f_{\widehat{j}}(x^{\prime})-\widehat{f}(x^{\prime}))|\right]$
(98)
$\displaystyle\leq\mathbb{E}\left[\frac{2}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}(X_{i})}|\Xi(x^{\prime})(f^{*}(x^{\prime})-f_{\widehat{j}}(x^{\prime}))|\right]+\mathbb{E}\left[\frac{2}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}(X_{i})}|\Xi(x^{\prime})(f_{\widehat{j}}(x^{\prime})-\widehat{f}(x^{\prime}))|\right]$
(99)
$\displaystyle\leq\mathbb{E}\left[\frac{2}{n}\sum_{i=1}^{n}\max_{x^{\prime}\in\Delta_{h}(X_{i})}|\Xi(x^{\prime})(f^{*}(x^{\prime})-f_{\widehat{j}}(x^{\prime}))|\frac{\|\widehat{f}-f^{*}\|_{L^{\infty}}+\delta}{\|f_{\widehat{j}}-f^{*}\|_{L^{\infty}}}\right]$
(100)
$\displaystyle\quad+2\mathbb{E}\left[\sup_{Q_{n}}\|\Xi\|_{L^{2}(Q_{n})}^{2}\right]^{1/2}\mathbb{E}\left[\sup_{Q_{n}}\|f_{\widehat{j}}-\widehat{f}\|_{L^{2}(Q_{n})}^{2}\right]^{1/2}$
(101)
$\displaystyle\leq\mathbb{E}\Biggl{[}\left(\|\widehat{f}-f^{*}\|_{L^{\infty}}+\delta\right)\underbrace{\frac{2}{n}\sum_{i=1}^{n}\frac{\max_{x^{\prime}\in\Delta_{h}(X_{i})}|\Xi(x^{\prime})(f^{*}(x^{\prime})-f_{\widehat{j}}(x^{\prime}))|}{\|f_{\widehat{j}}-f^{*}\|_{L^{\infty}}}}_{=:Z_{\widehat{j}}}\Biggr{]}+2\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]^{1/2}\delta.$
(102)

Since we have

$\displaystyle|Z_{j}|\leq\frac{2}{n}\sum_{i=1}^{n}\left|\frac{\max_{x^{\prime}\in\Delta_{h}(X_{i})}\\{|\Xi(x^{\prime})||(f^{*}(x^{\prime})-f_{{j}}(x^{\prime}))|\\}}{\|f_{{j}}-f^{*}\|_{L^{\infty}}}\right|\leq
2\|\Xi\|_{L^{\infty}},$ (103)

for any $j=1,...,N$, the Cauchy-Schwartz inequality yields

$\displaystyle\mathbb{E}\left[\left(\|\widehat{f}-f^{*}\|_{L^{\infty}}+\delta\right)Z_{\widehat{j}}\right]$
$\displaystyle\leq\mathbb{E}\left[\left(\|\widehat{f}-f^{*}\|_{L^{\infty}}+\delta\right)^{2}\right]^{1/2}\mathbb{E}\left[Z_{\widehat{j}}^{2}\right]^{1/2}$
(104) $\displaystyle\leq
2\left(\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]^{1/2}+\delta\right)\mathbb{E}\left[\max_{j=1,...,N_{L,W}(\delta)}Z_{j}^{2}\right]^{1/2}$
(105) $\displaystyle\leq
4\left(\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]^{1/2}+\delta\right)\left(\frac{\log
N_{L,W}(\delta)+\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]}{n}\right)^{1/2}.$
(106)

The last inequality follows the maximal inequality (Theorem 3.1.10 in [17])
for the bounded random process. Using this result, we obtain

$\displaystyle\mathbb{E}[T_{1}]$ $\displaystyle\leq
4\left(\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]^{1/2}+\delta\right)\left(\frac{\log
N_{L,W}(\delta)+\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]}{n}\right)^{1/2}+2\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]^{1/2}\delta$
(107)
$\displaystyle\leq\left(4\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]^{1/2}+10\delta\right)\left(\frac{\log
N_{L,W}(\delta)}{n}+\mathbb{E}\left[\|\Xi\|_{L^{\infty}}^{2}\right]\right)^{1/2}.$
(108)

We substitute the bound (108) into the expectation of (97), then obtain the
statement. ∎

###### Proof of Theorem 2.

Fix $\varepsilon>0$ arbitrary. Also, we fix $C_{*}=C_{P_{X},p,d,B}$ as used in
the statement of Proposition 8.

By the universal approximation theorem (e.g. Theorem 1 in [37]) associate with
the continuity of $f^{*}$, there exists a tuple $(L^{\prime},W^{\prime})$ such
that

$\displaystyle\Phi_{L^{\prime},W^{\prime}}\leq\sqrt{\varepsilon
h^{d}/(4C_{*})}.$ (109)

Further, by Assumption 3, there exists $\bar{n}\in\mathbb{N}$ such that

$\displaystyle\mathbb{E}[\|\Xi\|_{L^{\infty}}^{2}]\leq\sqrt{\varepsilon
h^{2d}/(4C_{*})}.$ (110)

Then, for all $n\geq\bar{n}$, Proposition 8 yields that

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]\leq
C_{*}h^{-d}\frac{(W^{\prime}L^{\prime})^{2}\log(W^{\prime}L^{\prime})\log
n}{n}+\frac{3\varepsilon}{4}.$ (111)

Then, for any $n\geq
n^{\prime}\vee(4C_{*}(W^{\prime}L^{\prime})^{2}\log(W^{\prime}L^{\prime})h^{-d}\varepsilon^{-1})$,
we have
$\mathbb{E}[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}]\leq\varepsilon/4+3\varepsilon/4=\varepsilon$,
which shows the statement. ∎

###### Proof of Theorem 3.

As preparation, Lemma 20 gives the following bound

$\displaystyle\Phi_{L,W}\leq C_{d,\beta}(LW)^{-2\beta/d}.$ (112)

With this bound on $\Phi_{L,W}$, we apply Proposition 8 and obtain

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]$
(113) $\displaystyle\leq
C_{P_{X},p,d,B,d,\beta}h^{-d}\left(\frac{(WL)^{2}\log(WL)\log
n}{n}+(LW)^{-4\beta/d}+\mathbb{E}[\|\Xi\|_{L^{\infty}}](LW)^{-2s/d}+h^{-d}\mathbb{E}[\|\Xi\|_{L^{\infty}}^{2}]\right).$

Further, we have

$\displaystyle(LW)^{-4\beta/d}+\mathbb{E}[\|\Xi\|_{L^{\infty}}](LW)^{-2s/d}+h^{-d}\mathbb{E}[\|\Xi\|_{L^{\infty}}^{2}]\leq\left\\{(LW)^{-2\beta/d}+h^{-d/2}\mathbb{E}[\|\Xi\|_{L^{\infty}}^{2}]^{1/2}\right\\}^{2},$
(114)

by applying Jensen’s inequality. Arranging the terms, we obtain the statement.
∎

###### Proof of Corollary 4.

We start with the inequality (113) in the proof of Theorem 3 and obtain

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]$
(115) $\displaystyle\leq
C_{P_{X},p,d,B,d,\beta}h^{-d}\left(n^{-2\beta/(2\beta+d)}(\log^{2}n+1)+\mathbb{E}[\|\Xi\|_{L^{\infty}}]n^{-\beta/(2\beta+d)}+h^{-d}\mathbb{E}[\|\Xi\|_{L^{\infty}}^{2}]\right)$
(116)

by the setting $WL\asymp n^{d/(4s+2d)}$. ∎

##  Appendix B Proof for Applications

###  B.1. Proof for General Loss Setting

We give proofs of the result in Section 5.

######  Proposition 13.

Consider the setting in Proposition 6. Then, we have for $n$ such that $\log
N(1/n)\geq 1$:

$\displaystyle\mathbb{E}\left[\widetilde{R}(\widetilde{f})-\widetilde{R}(f^{*})\right]\leq\frac{C_{\ell,B}(\log
N_{L,W}(1/n)+V^{2})}{n^{1/2}}+C_{\ell}(\Phi_{L,W}+\mathbb{E}[\|\Xi_{n}\|_{L^{\infty}}]).$
(117)

This proof is similar to Lemma 3.1 in [57]. A difference between [57] and our
result is that a property of the loss depends on $f$ in our setting, so we
have to modify it. Hence, we write down the proof.

###### Proof of Proposition 13.

We develop the proof in the following four steps: (i) a basic decomposition,
(ii) bounding a variance, (iii) bounding a bias, and (iv) combining every
bound.

Step 1: Basic decomposition. We define i.i.d. copies of the observations
$D:=\\{(X_{i},Y_{i})_{i=1}^{n}\\}$ as
$D^{\prime}:=\\{(X_{i}^{\prime},Y_{i}^{\prime})_{i=1}^{n}\\}$, and also define
an excess loss as

$\displaystyle
g(x,\widehat{Y},f)=\sup_{x^{\prime}\in\Delta_{h}^{p}(x)}\ell(f(x^{\prime}),\widehat{Y}(x^{\prime}))-\sup_{x^{\prime}\in\Delta_{h}^{p}(x)}\ell(f^{*}(x^{\prime}),\widehat{Y}(x^{\prime}))$
(118)

We further define empirical means of the excess loss as
$G_{n}(f):=n^{-1}\sum_{i=1}^{n}g(X_{i},\widehat{Y},f)$ with the observations
$D$, and
$G_{n}^{\prime}(f):=n^{-1}\sum_{i=1}^{n}g(X_{i}^{\prime},\widehat{Y},f)$ with
the copies $D^{\prime}$. Since $\widehat{f}$ is independent to $D^{\prime}$,
we can rewrite the expected risk as

$\displaystyle\mathbb{E}\left[\widetilde{R}(\widehat{f})-\widetilde{R}(f^{*})\right]=\mathbb{E}\left[\mathbb{E}_{D^{\prime}}\left[G_{n}^{\prime}(\widehat{f})\right]\right].$
(119)

Since $\widehat{f}$ is the minimizer of the empirical risk and the loss is
bounded, we obtain the following inequality of expectations:

$\displaystyle\mathbb{E}\Bigl{[}G_{n}(\widehat{f})\Bigr{]}\leq\mathbb{E}\Bigl{[}G_{n}({f})\Bigr{]},$
(120)

for any ${f}\in\mathcal{F}(L,W)$. We set set $\bar{f}$ such that
$\|\bar{f}-f^{*}\|_{L^{\infty}}=\inf_{f\in\mathcal{F}(L,W)}\|f-f^{*}\|_{L^{\infty}}$
Using this fact, we decompose the excess risk as

$\displaystyle\mathbb{E}\Bigl{[}\widetilde{R}(\widehat{f})-\widetilde{R}(\bar{f})\Bigr{]}$
$\displaystyle=\mathbb{E}\left[\mathbb{E}_{D^{\prime}}\left[G_{n}^{\prime}(\widehat{f})\right]\right]\leq\mathbb{E}\Bigl{[}\underbrace{-2G_{n}(\widehat{f})+\mathbb{E}_{D^{\prime}}\left[G_{n}^{\prime}(\widehat{f})\right]}_{=:\mathcal{V}}\Bigr{]}+2\mathbb{E}\Bigl{[}\underbrace{G_{n}(\bar{f})}_{=:\mathcal{B}}\Bigr{]}.$
(121)

The inequality follows (120).

Step 2: Bound the variance $\mathbb{E}[\mathcal{V}]$. We bound an expectation
of the term $\mathcal{V}$. By the boundedness of both $\widehat{Y}$ and
$\widetilde{f}$ by Assumption 3 and (14), the expectation
$\mathbb{E}[\mathcal{V}]$ exists.

We prepare additional notations. Fix $\delta\in(0,1]$. We consider a covering
set $\\{f_{j}\\}_{j=1}^{N_{L,W}(\delta)}\subset\mathcal{F}$, then we pick
$f_{j}$ from the set such that
$\sup_{Q_{n}}\|f_{j}-\widetilde{f}\|_{L^{2}(Q_{n})}\leq\delta$. We define a
term $\widetilde{g}(X_{i},\widehat{Y},\widetilde{f})$ by the following reform
of $\mathcal{V}$ as

$\displaystyle\mathcal{V}=\frac{1}{n}\sum_{i=1}^{n}\left\\{\mathbb{E}_{D^{\prime}}\left[G_{n}^{\prime}(\widetilde{f})\right]-2g(X_{i},\widehat{Y},\widetilde{f})\right\\}=:\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y},\widetilde{f}),$
(122)

which yields the following form

$\displaystyle\mathbb{E}[\mathcal{V}]$
$\displaystyle=\mathbb{E}\Biggl{[}\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y},\widetilde{f})\Biggr{]}$
(123)
$\displaystyle=\mathbb{E}\Biggl{[}\underbrace{\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y},f_{j})}_{:=\mathcal{V}_{1}}\Biggr{]}+\mathbb{E}\Biggl{[}\underbrace{\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y},\widetilde{f})-\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y},f_{j})}_{=:\mathcal{V}_{2}}\Biggr{]}.$
(124)

We will bound both $\mathbb{E}[\mathcal{V}_{1}]$ and
$\mathbb{E}[\mathcal{V}_{2}]$, separately.

We bound the term $\mathbb{E}[\mathcal{V}_{2}]$. Since $g$ in (118) is
Lipschitz continuous in $f$ with its Lipschitz constant $C_{\ell}$ by Lemma
19, we easily see that $\widetilde{g}$ is Lipschitz continuous in $f$ with its
Lipschitz constant $6C_{\ell}$. Thus, we obtain that

$\displaystyle\mathbb{E}[\mathcal{V}_{2}]\leq\left|\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y},\widetilde{f})\right]-\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y},{f}_{j})\right]\right|\leq
6C_{\ell}\delta.$ (125)

Next, we bound the term $\mathbb{E}[\mathcal{V}_{1}]$. Here, we need to
consider a uniformly bounded function $y:[0,1]^{d}\to[-B,B]$ For each $f_{j}$
in the covering set, $t>0$, and the bounded function $y$, we use the Bernstein
inequality to derive its stochastic upper bound. As preparation, we consider a
threshold $B_{n}\geq 1$ depending on $n$ and define a clipped preprocessing
$\widehat{Y}_{B_{n}}(\cdot):=\max\\{\min\\{\widehat{Y}(\cdot),B_{n}\\},-B_{n}\\}$.
We firstly approximate $\mathbb{E}[\mathcal{V}_{1}]$ by the Lipschitz
continuity of $\ell$ as

$\displaystyle\mathbb{E}[\mathcal{V}_{1}]\leq\mathbb{E}\Biggl{[}\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y}_{B_{n}},f_{j})\Biggr{]}+6C_{\ell}\mathbb{E}\left[\|\widehat{Y}-\widehat{Y}_{B_{n}}\|_{L^{\infty}}\right].$
(126)

Since
$|\widehat{Y}(x)-\widehat{Y}_{B_{n}(x)}|=|\widehat{Y}(x)|\textbf{1}\\{|\widehat{Y}(x)|\geq
B_{n}\\}$ holds, we can bound the expectation in the second term of the right-
hand side as

$\displaystyle\mathbb{E}\left[\|\widehat{Y}-\widehat{Y}_{B_{n}}\|_{L^{\infty}}\right]$
$\displaystyle=\mathbb{E}\left[\sup_{x\in[0,1]^{d}}|\widehat{Y}(x)|\textbf{1}\\{|\widehat{Y}(x)|\geq
B_{n}\\}|\right]$ (127)
$\displaystyle\leq\mathbb{E}\left[\sup_{x\in[0,1]^{d}}|\widehat{Y}(x)|\sup_{x\in[0,1]^{d}}\textbf{1}\\{|\widehat{Y}(x)|\geq
B_{n}\\}|\right]$ (128)
$\displaystyle\leq\mathbb{E}\left[\|\widehat{Y}\|_{L^{\infty}}\textbf{1}\\{\|\widehat{Y}\|_{L^{\infty}}\geq
B_{n}\\}\right]$ (129)
$\displaystyle\leq\mathbb{E}\left[\|\widehat{Y}\|_{L^{\infty}}^{2}/B_{n}\right].$
(130)

The last inequality follows $\textbf{1}\\{x\geq 1\\}\leq x$ for any $x\geq 0$.
The existence of the second moment is guaranteed by Assumption 3. We put this
result to (126) and obtain

$\displaystyle\mathbb{E}[\mathcal{V}_{1}]\leq\mathbb{E}\Biggl{[}\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y}_{B_{n}},f_{j})\Biggr{]}+6C_{\ell}\mathbb{E}\left[\|\widehat{Y}\|_{L^{\infty}}^{2}/B_{n}\right].$
(131)

Then, we bound the first term
$\mathbb{E}[n^{-1}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y}_{B_{n}},f_{j})]$.
Since we have $|g(x,\widehat{Y}_{B_{n}},f)|\leq C_{\ell}(B_{n}\vee B)$ for any
$x\in[0,1]^{d}$ and $f:\|f\|_{L^{\infty}}\leq B$, we obtain the following
inequality with fixed $\widehat{Y}_{B_{n}}$:

$\displaystyle\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y}_{B_{n}},{f}_{j})>t\right)$
(132)
$\displaystyle=\mathbb{P}\left(\mathbb{E}_{D^{\prime}}\left[g(X_{i}^{\prime},\widehat{Y}_{B_{n}},{f}_{j})\right]-\frac{2}{n}\sum_{i=1}^{n}g(X_{i},\widehat{Y}_{B_{n}},{f}_{j})>t\right)$
(133)
$\displaystyle=\mathbb{P}\left(\mathbb{E}_{D^{\prime}}\left[g(X_{i}^{\prime},\widehat{Y}_{B_{n}},{f}_{j})\right]-\frac{1}{n}\sum_{i=1}^{n}g(X_{i},\widehat{Y}_{B_{n}},{f}_{j})>\frac{t}{2}+\frac{1}{2}\mathbb{E}_{D^{\prime}}\left[g(X_{i}^{\prime},\widehat{Y}_{B_{n}},{f}_{j})\right]\right)$
(134)
$\displaystyle\leq\mathbb{P}\left(\mathbb{E}_{D^{\prime}}\left[g(X_{i}^{\prime},\widehat{Y}_{B_{n}},{f}_{j})\right]-\frac{1}{n}\sum_{i=1}^{n}g(X_{i},\widehat{Y}_{B_{n}},{f}_{j})>\frac{t}{2}+\frac{1}{2}\frac{\operatorname{Var}_{D^{\prime}}(g(X_{i},\widehat{Y}_{B_{n}},f_{j}))}{4C_{\ell}B_{n}}\right)$
(135)
$\displaystyle\leq\exp\left(-\frac{n(t^{\prime})^{2}}{2\operatorname{Var}_{D^{\prime}}(g(X_{i},\widehat{Y}_{B_{n}},f_{j}))+16C_{\ell}(B_{n}\vee
B)t^{\prime}/3}\right)$ (136)
$\displaystyle\leq\exp\left(-\frac{n(t^{\prime})^{2}}{2t^{\prime}C_{\ell}(B_{n}\vee
B)+C_{\ell}(B_{n}\vee B)t^{\prime}/3}\right)$ (137)
$\displaystyle\leq\exp\left(-\frac{n(t^{\prime})^{2}}{16t^{\prime}C_{\ell}(B_{n}\vee
B)+16C_{\ell}(B_{n}\vee B)t^{\prime}/3}\right)$ (138)
$\displaystyle\leq\exp\left(-\frac{3nt^{\prime}}{64C_{\ell}(B_{n}\vee
B)}\right)$ (139)
$\displaystyle\leq\exp\left(-\frac{3nt}{128C_{\ell}(B_{n}\vee B)}\right).$
(140)

The first and third inequalities follow
$\operatorname{Var}_{D^{\prime}}(g(X_{i},\widehat{Y}_{B_{n}},f_{j}))\leq
4C_{\ell}B_{n}\mathbb{E}_{D^{\prime}}[g(X_{i},\widehat{Y}_{B_{n}},f_{j})]$,
and the second and last inequalities follows a setting
$t^{\prime}=t/2+\operatorname{Var}_{D^{\prime}}(g(X_{i},\widehat{Y}_{B_{n}},f_{j}))/(8C_{\ell}(B\vee
B_{n}))$. Using this inequality for a uniform bound in terms of the covering
set $\\{f_{j}\\}_{j=1}^{N_{L,W}(\delta)}$ and the independent random functions
$\widehat{Y}$ and $\widehat{Y}_{B_{n}}$, we obtain

$\displaystyle\mathbb{P}\left(\max_{j=1,...,N_{L,W}(\delta)}\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y}_{B_{n}},{f}_{j})>t\right)\leq
N_{L,W}(\delta)\exp\left(-\frac{3nt}{128C_{\ell}(B_{n}\vee B)t}\right).$ (141)

Then, by the maximal inequality (Corollary 2.2.8 in [68]), for any $\eta>0$,
we have

$\displaystyle\mathbb{E}\left[\max_{j=1,...,N_{L,W}(\delta)}\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y}_{B_{n}},{f}_{j})\right]\right]$
(142)
$\displaystyle\leq\eta+\int_{\eta}^{\infty}\mathbb{P}\left(\max_{j=1,...,N_{L,W}(\delta)}\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y}_{B_{n}},{f}_{j})>t\right)dt$
(143)
$\displaystyle\leq\eta+\int_{\eta}^{\infty}N_{L,W}(\delta)\exp\left(-\frac{3nt}{128C_{\ell}(B_{n}\vee
B)t}\right)dt$ (144)
$\displaystyle\leq\eta+\frac{N_{L,W}(\delta)(128C_{\ell}(B_{n}\vee
B))}{3n}\exp\left(-\frac{3n\eta}{128C_{\ell}(B_{n}\vee B)}\right).$ (145)

We set $B_{n}=n^{1/2}$, hence we have $(B\vee B_{n})\leq C_{B}n^{1/2}$. Also,
we set $\eta=(128C_{B,\ell}n^{1/2})\log N_{L,W}(\delta)/(3n)$ and put this
result into (131), we obtain

$\displaystyle\mathbb{E}[\mathcal{V}_{1}]\leq\mathbb{E}\left[\max_{j=1,...,N}\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\widetilde{g}(X_{i},\widehat{Y},{f}_{j})\right]\right]\leq\frac{C_{\ell,B}(\log
N_{L,W}(\delta)+\mathbb{E}[\|\widehat{Y}\|_{L^{\infty}}^{2}])}{n^{1/2}}.$
(146)

Combining the inequalities (125) and (146) into (124) and set $\delta=1/n$, we
obtain

$\displaystyle\mathbb{E}[\mathcal{V}]\leq\frac{(2C_{\ell}^{2}B_{2}+C_{\ell}B/3)(\log
N_{L,W}(1/n)+\mathbb{E}[\|\widehat{Y}\|_{L^{\infty}}^{2}])}{n^{1/2}}.$ (147)

Step 3: Bound the bias $\mathbb{E}[\mathcal{B}]$. By the Lipschitz continuity
of the loss $\ell$ by Assumption 4, we have

$\displaystyle\mathbb{E}[\mathcal{B}]$
$\displaystyle=\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\sup_{x^{\prime}\in\Delta_{h}^{p}(X_{i})}\ell(\bar{f}(x^{\prime}),\widehat{Y}(x^{\prime}))\right]$
(148)
$\displaystyle\leq\mathbb{E}\left[\sup_{x\in[0,1]^{d}}\ell(\bar{f}(x),\widehat{Y}(x))\right]$
(149)
$\displaystyle\leq\mathbb{E}\left[\sup_{x^{\prime}\in[0,1]^{d}}C_{\ell}|\bar{f}(x)-\widehat{Y}(x)|+\ell(\widehat{Y}(x),\widehat{Y}(x))\right]$
(150) $\displaystyle\leq
C_{\ell}\mathbb{E}\left[\|\bar{f}-\widehat{Y}\|_{L^{\infty}}\right]$ (151)
$\displaystyle\leq
C_{\ell}(\|\bar{f}-f^{*}\|_{L^{\infty}}+\mathbb{E}[\|f^{*}-\widehat{Y}\|_{L^{\infty}}])$
(152) $\displaystyle\leq
C_{\ell}(\Phi_{L,W}+\mathbb{E}[\|\Xi_{n}\|_{L^{\infty}}]).$ (153)

The last inequality holds by setting $\bar{f}$ such that
$\|\bar{f}-f^{*}\|_{L^{\infty}}=\inf_{f\in\mathcal{F}(L,W)}\|f-f^{*}\|_{L^{\infty}}$.

Step 4: Combining the bounds. We combine the result in Step 3 and Step 4 into
the decomposition (121), then obtain the statement. ∎

######  Lemma 14.

Consider the expected adversarial risk $\widetilde{R}(\cdot)$ with general
losses as (38). Then, for the estimator $\widetilde{f}$ as (36) and
$q\in[1,\infty)$, we have

$\displaystyle\|f^{*}-\widetilde{f}\|_{L^{\infty}}^{q}\leq
C_{P_{X},p,d,\ell,q}h^{-d}\left(\widetilde{R}(\widetilde{f})-\widetilde{R}(f^{*})+\|\Xi\|_{L^{\infty}}^{q}\vee\|\Xi\|_{L^{\infty}}\right).$
(154)

###### Proof of Lemma 14.

We develop a lower bound of
$\widetilde{R}(\widetilde{f})-\widetilde{R}(f^{*})$ as

$\displaystyle\widetilde{R}(\widetilde{f})-\widetilde{R}(f^{*})$
$\displaystyle=\mathbb{E}_{X}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}\ell(\widehat{Y}(x^{\prime}),\widetilde{f}(x^{\prime}))-\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}\ell(\widehat{Y}(x^{\prime}),f^{*}(x^{\prime}))\right]$
(155) $\displaystyle\geq
C_{P_{X},p,d}h^{d}\sup_{x\in[0,1]^{d}}|\ell(\widehat{Y}(x^{\prime}),\widetilde{f}(x^{\prime}))|-C_{\ell}\|\widehat{Y}-f^{*}\|_{L^{\infty}}$
(156) $\displaystyle\geq
C_{P_{X},p,d,\ell}h^{d}\|\widehat{Y}-\widetilde{f}\|_{L^{\infty}}^{q}-C_{\ell}\|\Xi\|_{L^{\infty}}$
(157) $\displaystyle\geq
C_{P_{X},p,d,\ell,q}h^{d}\left(\|f^{*}-\widetilde{f}\|_{L^{\infty}}^{q}-\|\Xi\|_{L^{\infty}}^{q}\right)-C_{\ell}\|\Xi\|_{L^{\infty}}.$
(158)

Here, the first inequality follows Lemma 15 and the Lipschitz continuity of
$\ell$ by Assumption 4, and the last inequality follows $(a+b)^{q}\leq
C_{q}(a^{q}+b^{q})$ for $q\in[1,\infty)$ and $a,b\geq 0$. ∎

###### Proof of Proposition 6.

By Proposition 13 and Lemma 14, we have

$\displaystyle\mathbb{E}\left[\|f^{*}-\widetilde{f}\|^{2}_{L^{\infty}}\right]$
$\displaystyle\leq
C_{P_{X},p,d,\ell,q}h^{-2d/q}\left(\mathbb{E}[(\widetilde{R}(\widetilde{f})-\tilde{R}(f^{*}))^{2/q}]+\mathbb{E}[\|\Xi\|_{L^{\infty}}^{2}]\right)$
(159) $\displaystyle\leq
C_{P_{X},B,p,d,\ell,q,}h^{-2d/q}\left\\{\left(\frac{\log
N_{L,W}(1/n)}{n^{1/2}}\right)^{2/q}+\Phi_{L,W}^{2/q}+\zeta_{n}^{2}\right\\}$
(160) $\displaystyle\leq
C_{P_{X},B,p,d,\ell,q,V}h^{-2d/q}\left\\{\left(\frac{W^{2}L^{2}\log(WL)\log
n}{n^{1/2}}\right)^{2/q}+\Phi_{L,W}^{2/q}+\zeta_{n}^{2}\right\\}.$ (161)

The last inequality follows Lemma 16. We set $WL\asymp n^{d/(4\beta+4d)}$ and
obtain the statement. ∎

###  B.2. Proof of Adaptation to Besov Space

We give proof of the result in Section 5.2.

###### Proof of Proposition 7.

To show the statement, we slightly modify the proof of Proposition 8. We start
from the inequality (60) with setting $\delta=1/n$. Since we use
$\overline{\mathcal{F}}(L,W,S,\bar{B})$ as a set of candidate functions
instead of $\mathcal{F}(L,W)$, we obtain the following updated inequality of
(60) as

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]\leq
C_{P_{X},p,d,B}h^{-d}\Biggl{\\{}\frac{\log\widetilde{N}_{L,W,S,\bar{B}}(1/n)}{n}+\widetilde{\Phi}_{L,W,S,\bar{B}}^{2}+\zeta_{n}^{2}\Biggr{\\}},$
(162)

which replaces $N_{L,W}(1/n)$ by
$\widetilde{N}_{L,W,S,\bar{B}}(1/n):=\sup_{Q_{n}}N(1/n,\overline{\mathcal{F}}(L,W,S,\bar{B}),\|\cdot\|_{L^{2}(Q_{n})})$
and ${\Phi}_{L,W}$ by
$\widetilde{\Phi}_{L,W,S,\bar{B}}:=\inf_{f\in\overline{\mathcal{F}}(L,W,S,\bar{B})}\|f-f^{*}\|_{L^{\infty}}$.

We study the terms $\widetilde{N}_{L,W,S,\bar{B}}(1/n)$ and
$\widetilde{\Phi}_{L,W,S,\bar{B}}$. For the approximation error term
$\widetilde{\Phi}_{L,W,S,\bar{B}}$, we apply Lemma 21 by setting $r=\infty$
and obtain

$\displaystyle\widetilde{\Phi}_{L,W,S,\bar{B}}\leq C_{d,\beta}N^{-\beta/d},$
(163)

for sufficiently large $N$ such that $L\geq C_{d,p,\beta,B}\log(N)$,
$W=C_{d,\beta}N$, $S=(L-1)C_{d,\beta}N+N$. About the entropy term
$\widetilde{N}_{L,W,S,\bar{B}}(1/n)$, we apply Lemma 22 and obtain

$\displaystyle\log\widetilde{N}_{L,W,S,\bar{B}}(1/n)$ $\displaystyle\leq\log
N(1/n,\overline{\mathcal{F}}(L,W,S,\bar{B}),\|\cdot\|_{L^{\infty}})$ (164)
$\displaystyle\leq LS\log(nL\bar{B}(1+S))$ (165) $\displaystyle\leq
C_{d,\beta}L^{2}N\log(nL^{2}\bar{B}N)$ (166) $\displaystyle\leq
C_{d,p,\beta,B}N\log^{2}(N)\log(nN\log^{2}(N)),$ (167)

by substituting the setup of $L,S,W$ and $\bar{B}$.

We substitute (163) and (167) into (162) and obtain

$\displaystyle\mathbb{E}\left[\|\widehat{f}-f^{*}\|_{L^{\infty}}^{2}\right]\leq
C_{P_{X},p,d,B,\beta}h^{-d}\Biggl{\\{}\frac{N\log^{2}(N)\log(nN\log^{2}(N))}{n}+N^{-2\beta/d}+\zeta_{n}^{2}\Biggr{\\}}.$
(168)

We set $N\asymp n^{d/(2\beta+d)}$ and obtain the statement. ∎

##  Appendix C Supportive Result

######  Lemma 15.

Consider a non-negative bounded continuous function
$g:[0,1]^{d}\to\mathbb{R}_{+}$. Then, we have

$\displaystyle\mathbb{E}_{X}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}g(x^{\prime})\right]\geq\|g\|_{L^{\infty}}P_{X}(\Delta_{h}^{p}(x^{*})),$
(169)

with $x^{*}\in\operatornamewithlimits{argmax}_{x\in[0,1]^{d}g(x)}$. Further,
if Assumption 1 holds, then we have

$\displaystyle\mathbb{E}_{X}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}g(x^{\prime})\right]\geq\|g\|_{L^{\infty}}h^{d}C_{P_{X},p,d}.$
(170)

###### Proof of Lemma 15.

Let $A:=\\{x\in[0,1]^{d}\mid
g(x)=\max_{x^{\prime}\in[0,1]^{d}}g(x^{\prime})\\}$ be a set of argmax of
$g(x)$, which is non-empty because of the compactness of $[0,1]^{d}$ and
boundedness/continuity of $g$. Also, we define a union $\Delta_{A}:=\cup_{x\in
A}\Delta_{h}^{p}(\\{x\\})$.

By the non-negativity of $g$, we obtain

$\displaystyle\mathbb{E}_{X}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}g(x^{\prime})\right]$
$\displaystyle\geq\mathbb{E}_{X}\left[\sup_{x^{\prime}\in\Delta_{h}^{p}(X)}g(x^{\prime})\textbf{1}\\{X\in\Delta_{A}\\}\right]$
(171)
$\displaystyle=\mathbb{E}_{X}\left[\sup_{x\in[0,1]^{d}}g(x)\textbf{1}\\{X\in\Delta_{A}\\}\right]$
(172) $\displaystyle=\|g\|_{L^{\infty}}P_{X}(\Delta_{A}).$ (173)

Hence, we obtain the first statement.

We consider that Assumption 1 holds. We develop a lower bound of
$P_{X}(\Delta_{A})$ as

$\displaystyle P_{X}(\Delta_{A})\geq\inf_{x\in
A}P_{X}(\Delta_{h}^{p}(\\{x\\}))\geq C_{P_{X}}\inf_{x\in
A}P_{X}(\Delta_{h}^{p}(\\{x\\}))\geq
C_{P_{X}}\inf_{x\in[0,1]^{d}}\lambda(\Delta_{h}^{p}(\\{x\\})),$ (174)

where $C_{P_{X}}$ is a lower bound of a density function of $P_{X}$ defined in
Assumption 1, and $\lambda(\cdot)$ is the Lebesgue measure. Since the Lebesgue
of the $L^{p}$-ball is known, we obtain that

$\displaystyle\inf_{x\in[0,1]^{d}}\lambda(\Delta_{h}^{p}(\\{x\\}))=\frac{\Gamma(1/p+1)^{d}}{\Gamma(d/p+1)}h^{d},$
(175)

where $\Gamma(\cdot)$ is the Gamma function. Then, we obtain the second
statement. ∎

We develop the following covering number bound. The following lemma
immediately holds by [1] and [22].

######  Lemma 16.

Consider the set of deep neural networks as (14) with the depth $L$, the width
$W$, and the upper bound $B$. For any $\delta>0$ and sufficiently large $n$,
we have

$\displaystyle\log N(\delta,\mathcal{F}(L,W),\|\cdot\|_{L^{2}(P_{n})})\leq
CW^{2}L^{2}\log(WL)\log(Bn/\delta).$ (176)

###### Proof of Lemma 16.

Let $D$ be the VC-dimension of $\mathcal{F}$, and $S(\leq W^{2}L)$ be a number
of parameters in $\mathcal{F}$. By Theorem 3 in [22], we bound the VC-
dimension as $D=O(SL\log(S))\leq O(W^{2}L^{2}\log(WL))$. Using this inequality
and Theorem 12.2 in [1], we have

$\displaystyle\log N(\delta,\mathcal{F}(L,W),\|\cdot\|_{L^{2}(P_{n})})\leq
D\log\left(\frac{enB}{\delta D}\right)\leq
CW^{2}L^{2}\log(WH)\log(Bn/\delta).$ (177)

for $n=\Omega(W^{2}H^{2}\log(WH))$. ∎

######  Lemma 17.

Consider a non-empty compact set $T\subset\mathbb{R}^{d}$ with some $d$ and
continuous bounded functions $f,f^{\prime}:T\to\mathbb{R}$. Then, we have

$\displaystyle\left|\sup_{t\in T}(f(t)+f^{\prime}(t))^{2}-\sup_{t\in
T}f(t)\right|\leq\|f\|_{L^{\infty}}\|f^{\prime}\|_{L^{\infty}}+\|f^{\prime}\|_{L^{\infty}}^{2}.$
(178)

###### Proof of Lemma 17.

We define the optimal values $t^{*}\in T$ and $t^{\dagger}\in T$ such that
$\sup_{t\in T}(f(t)+f^{\prime}(t))^{2}=(f(t^{*})+f^{\prime}(t^{*}))^{2}$ and
$\sup_{t\in T}f(t)^{2}=f(t^{\dagger})^{2}$. Note that such $t^{*}\in T$ and
$t^{\dagger}\in T$ exist by the compactness of $T$ and the continuity of $f$
and $f^{\prime}$.

We first derive the following inequality

$\displaystyle\sup_{t\in T}(f(t)+f^{\prime}(t))^{2}-\sup_{t\in T}f(t)^{2}$
$\displaystyle\leq
f(t^{*})^{2}+2f(t^{*})f^{\prime}(t^{*})+f^{\prime}(t^{*})^{2}-f(t^{*})^{2}$
(179) $\displaystyle\leq
2\|f\|_{L^{\infty}}\|f^{\prime}\|_{L^{\infty}}+\|f^{\prime}\|_{L^{\infty}}^{2}.$
(180)

Second, we develop a bound for the opposite side as

$\displaystyle\sup_{t\in T}f(t)^{2}-\sup_{t\in T}(f(t)+f^{\prime}(t))^{2}$
$\displaystyle\leq
f(t^{\dagger})^{2}-(f(t^{\dagger})+f^{\prime}(t^{\dagger}))^{2}$ (181)
$\displaystyle\leq
2f(t^{\dagger})f^{\prime}(t^{\dagger})-f^{\prime}(t^{\dagger})^{2}$ (182)
$\displaystyle\leq
2\|f\|_{L^{\infty}}\|f^{\prime}\|_{L^{\infty}}+\|f^{\prime}\|_{L^{\infty}}^{2}.$
(183)

Then, we obtain the statement. ∎

######  Lemma 18.

For any continuous and bounded functions $f,g$ on a compact set $I$, we have

$\displaystyle\max_{t\in I}(f(t)+g(t))\geq\max_{t\in I}f(t)-\max_{t\in
I}|g(t)|.$ (184)

###### Proof of Lemma 18.

Let $t^{\prime}\in I$ be a point such that $\max_{t\in
I}(f(t)+g(t))=f(t^{\prime})+g(t^{\prime})$, which is guaranteed to exist by
the compactness of $I$ and the boundedness/continuity of $f,g$. The statement
simply follows

$\displaystyle\max_{t}(f(t)+g(t))$
$\displaystyle=f(t^{\prime})+g(t^{\prime})\geq
f(t^{\prime})-|g(t^{\prime})|\geq\max_{t}(f(t))-\max_{t}|g(t^{\prime})|.$
(185)

∎

######  Lemma 19.

Consider functions $f,f^{\prime},y:[0,1]^{d}\to[-B,B]$, and a loss function
$\ell$ satisfying Assumption 4. Also, consider a funciton $g$ as (118). For
any $x\in[0,1]^{d}$, we have

$\displaystyle g(x,y,f)-g(x,y,f^{\prime})\leq
C_{\ell}|f(\bar{x})-f^{\prime}(\bar{x})|,$ (186)

for some $\bar{x}\in[0,1]^{d}$.

###### Proof of Lemma 19.

We define $x^{*}\in\Delta_{h}^{p}(x)$ such that
$\ell(y(x^{*}),f(x^{*}))=\max_{x^{\prime}\in\Delta_{x}}\ell(y(x^{\prime}),f(x^{\prime}))$.
Its existence follows the continuity of $f,f^{\prime},y$, and $\ell$. For
$f,f^{\prime}\in L^{2}([0,1]^{d})$, we have

$\displaystyle g(x,y,f)-g(x,y,f^{\prime})$
$\displaystyle=\max_{x^{\prime}\in\Delta_{h}^{p}(x)}\ell(y(x^{\prime}),f(x^{\prime}))-\max_{x^{\prime}\in\Delta_{h}^{p}(x)}\ell(y(x^{\prime}),f^{\prime}(x^{\prime}))$
(187)
$\displaystyle\leq\ell(y(x^{*}),f(x^{*}))-\ell(y(x^{*}),f^{\prime}(x^{*}))$
(188) $\displaystyle\leq C_{\ell}|f(x^{*})-f^{\prime}(x^{*})|.$ (189)

The first inequality follows
$\max_{x^{\prime}\in\Delta_{h}^{p}(x)}\ell(y(x^{\prime}),f(x^{\prime}))=\ell(y(x^{*}),f(x^{*}))$,
and the second inequality follows the Lipschitz continuity of $\ell$ in the
second argument from Assumption 4. Thus, we obtain the statement. ∎

######  Lemma 20 (Theorem 1.1 in [39]).

Fix $N,M\in\mathbb{N}$ arbitrarily. If $\mathcal{F}(L,W)$ is a set of
functions with $W=C_{d}(N+2)\log_{2}(8N)$ and $L=C_{s}(M+2)\log_{2}(4M)+2d$,
we have

$\displaystyle\inf_{f\in\mathcal{F}}\sup_{f^{*}\in
C^{s}_{1}([0,1]^{d})}\|f-f^{*}\|_{L^{\infty}}\leq C_{d,s}N^{-2s/d}M^{-2s/d}.$
(190)

######  Lemma 21 (Proposition 1 in [63]).

Fix $p,q,r\in(0,\infty]$ and $\beta\in(0,\infty)$. Suppose that
$\beta>d\max\\{1/p-1/r,0\\}$ holds. Let
$\overline{\mathcal{F}}(L,W,S,\bar{B})$ be a set of neural network functions
(14) such that there are $S\in\mathbb{N}$ non-zero parameters and each value
is included in $[-\bar{B},\bar{B}]$ with $\bar{B}\geq 1$. Let $N$ be a
sufficiently large number and set $L\geq C_{d,p,\beta,B}\log(N)$,
$W=C_{d,\beta}N$, $S=(L-1)C_{d,\beta}N+N$, and $\bar{B}$ is a polynomially
increasing in $N$. Then, we have

$\displaystyle\sup_{f^{0}\in\mathcal{B}_{p,q}^{\beta}}\inf_{f\in\overline{\mathcal{F}}(L,W,S,\bar{B})}\|f^{0}-f\|_{L^{r}(\lambda)}\leq
CN^{-\beta/d},$ (191)

with some constant $C>0$ independent of $N$.

######  Lemma 22 (Lemma 21 in [45]).

For $\varepsilon\in(0,1]$, we obtain

$\displaystyle\log N(\varepsilon,\overline{{F}}(L,W,S,\bar{B}))\leq
LS\log(\varepsilon^{-1}L\bar{B}(1+S)).$ (192)

##  Appendix D Proof of Inconsistency

###### Proof of Proposition 1.

We first specify the coordinates of the setting. We consider two points
$\bar{x}=(0.3,0.5,0.5,...,0.5),\bar{x}^{\prime}=(0.7,0.5,0.5,...,0.5)\in[0,1]^{d}$,
and a marginal measure as a mixture of Dirac measures on the points;
$P_{X}=0.5\delta_{\\{\bar{x}\\}}+0.5\delta_{\\{\bar{x}^{\prime}\\}}$. We also
specify the true function with an input $x=(x_{1},...,x_{d})\in[0,1]^{d}$ as
$f^{*}(x)=-\textbf{1}\\{x_{1}<0.4\\}+10(x_{1}-0.5)\textbf{1}\\{0.4\leq
x_{1}\leq 0.6\\}+\textbf{1}\\{x_{1}>0.6\\}$, and the noise variable $\xi_{i}$
as a uniform random variable on $[-0.1,0.1]$. For the adversarial training, we
set $p=\infty$ and $h=0.5$.

We study an empirical risk minimizer in this setting. Since the inputs
$X_{1},...,X_{n}$ are either of $\bar{x}$ or $\bar{x}^{\prime}$, we set
$n_{1}:=|\\{i:X_{i}=\bar{x}\\}|$ and $n_{2}:=|\\{i:X_{i}=\bar{x}^{\prime}\\}|$
such that $n=n_{1}+n_{2}$. With the specified coordinates above, we rewrite an
empirical risk of $f:[0,1]^{d}\to\mathbb{R}$ with the adversarial training as

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\max_{x\in\Delta_{h}^{p}(X_{i})}(Y_{i}-f(x))^{2}$
$\displaystyle=\frac{1}{n}\sum_{i:X_{i}=\bar{x}}\max_{x\in\Delta_{h}^{p}(X_{i})}(f^{*}(X_{i})+\xi_{i}-f(x))^{2}+\frac{1}{n}\sum_{i:X_{i}=\bar{x}^{\prime}}\max_{x\in\Delta_{h}^{p}(X_{i})}(f^{*}(X_{i})+\xi_{i}-f(x))^{2}$
$\displaystyle=\frac{1}{n}\sum_{i:X_{i}=\bar{x}}\max_{x\in[0,1]^{d}:x_{1}\in[0,0.8]}(\xi_{i}-f(x))^{2}+\frac{1}{n}\sum_{i:X_{i}=\bar{x}^{\prime}}\max_{x\in[0,1]^{d}:x_{1}\in[0.2,1]}(1+\xi_{i}-f(x))^{2},$
(193)

which follows $f^{*}(\bar{x})=0$ and $f^{*}(\bar{x}^{\prime})=1$. To minimize
this empirical risk in terms of $f$, we restrict a class of $f$. Specifically,
we set $f$ with an input $x=(x_{1},...,x_{d})$ as having a form
$f(x)=c_{1}\textbf{1}\\{x_{1}\leq
0.2\\}+c_{2}\\{0.2<x_{1}<0.8\\}+c_{3}\textbf{1}\\{0.8\leq x_{1}\\}$ with some
constants $c_{1},c_{2},c_{3}\in\mathbb{R}$. This form of $f$ can minimize the
risk, since The risk depends only on the value of $f$ for each region. Then,
we rewrite the risk as

$\displaystyle\eqref{eq:rewrite_risk}$
$\displaystyle=\frac{1}{n}\sum_{i:X_{i}=\bar{x}}\max\\{(\xi_{i}-c_{1})^{2},(\xi_{i}-c_{2})^{2}\\}+\frac{1}{n}\sum_{i:X_{i}=\bar{x}^{\prime}}\max\\{(1+\xi_{i}-c_{2})^{2},(1+\xi_{i}-c_{3})^{2}\\}.$
(194)

Here, we consider an event $|n_{1}/2-n/2|\leq 1$, which appears with
probability $1-2\exp(-2/n)\geq 0.5$ with $n\geq 3$, by Hoeffding’s inequality.
In this case, a simple calculation yields that $c_{2}\in[-0.2,0.2]$ minimizes
the (194) since it prevents quadratic growth of the risk in terms of $c_{2}$,
which gives $(\xi_{i}-c_{1})^{2}<(\xi_{i}-c_{2})^{2}$ and
$(1+\xi_{i}-c_{2})^{2}>(1+\xi_{i}-c_{3})^{2}$. Then, we rewrite the risk (194)
as

$\displaystyle\eqref{eq:rewrite_risk2}=\frac{1}{n}\sum_{i:X_{i}=\bar{x}}(\xi_{i}-c_{2})^{2}+\frac{1}{n}\sum_{i:X_{i}=\bar{x}^{\prime}}(1+\xi_{i}-c_{2})^{2},$
(195)

and the minimization on it by $c_{2}$ yields the following optimal choise

$\displaystyle
c_{2}^{*}=\frac{n_{2}-n_{1}}{n}+\frac{1}{n}\sum_{i=1}^{n}\xi_{i}.$ (196)

Then, we have that the original risk (193) is minimized by the following
function

$\displaystyle\check{f}(x):=c_{1}^{*}\textbf{1}\\{x_{1}\leq
0.2\\}+c_{2}^{*}\\{0.2<x_{1}<0.8\\}+c_{3}^{*}\textbf{1}\\{0.8\leq x_{1}\\},$
(197)

where $c_{1}^{*}=n_{1}^{-1}\sum_{i:X_{i}=\bar{x}}\xi_{i}$ and
$c_{3}^{*}=n_{2}^{-1}\sum_{i:X_{i}=\bar{x}^{\prime}}\xi_{i}$.

Finally, we define the $L^{\infty}$-risk of $\check{f}$. Simply, we have

$\displaystyle\|\check{f}-f^{*}\|_{L^{\infty}}^{2}$
$\displaystyle\geq\|\check{f}-f^{*}\|_{L^{2}(P_{X})}^{2}$ (198)
$\displaystyle=\mathbb{E}_{X\sim
P_{X}}\left[(\check{f}(X)-f^{*}(X))^{2}\right]$ (199)
$\displaystyle=\frac{1}{2}\left\\{(\check{f}(\bar{x})-f^{*}(\bar{x}))^{2}+(\check{f}(\bar{x}^{\prime})-f^{*}(\bar{x}^{\prime}))^{2}\right\\}$
(200)
$\displaystyle=\frac{1}{2}\left\\{(c_{2}^{*}+1)^{2}+(c_{2}^{*}-1)^{2}\right\\}$
(201) $\displaystyle=1+(c_{2}^{*})^{2}$ (202) $\displaystyle\geq 1.$ (203)

Hence, we show the statement of Proposition 1. ∎

## References

  * AB [99] Martin Anthony and Peter L Bartlett.  Neural network learning: Theoretical foundations, volume 9.  cambridge university press Cambridge, 1999.
  * BCCK [15] Alexandre Belloni, Victor Chernozhukov, Denis Chetverikov, and Kengo Kato.  Some new asymptotic theory for least squares series: Pointwise and uniform results.  Journal of Econometrics, 186(2):345–366, 2015.
  * BK [19] Benedikt Bauer and Michael Kohler.  On deep learning as a remedy for the curse of dimensionality in nonparametric regression.  The Annals of Statistics, 47(4):2261–2285, 2019.
  * Cas [14] Ismaël Castillo.  On bayesian supremum norm contraction rates.  The Annals of Statistics, 42(5):2058–2091, 2014.
  * CC [15] Xiaohong Chen and Timothy M Christensen.  Optimal uniform convergence rates and asymptotic normality for series estimators under weak dependence and weak conditions.  Journal of Econometrics, 188(2):447–465, 2015.
  * CC [18] Xiaohong Chen and Timothy M Christensen.  Optimal sup-norm rates and uniform inference on nonlinear functionals of nonparametric iv regression.  Quantitative Economics, 9(1):39–84, 2018.
  * CJLZ [19] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao.  Efficient approximation of deep relu networks for functions on low dimensional manifolds.  Advances in neural information processing systems, 32, 2019.
  * Cox [88] Dennis D Cox.  Approximation of least squares regression on nested subspaces.  The Annals of Statistics, 16(2):713–732, 1988.
  * Cyb [89] George Cybenko.  Approximation by superpositions of a sigmoidal function.  Mathematics of control, signals and systems, 2(4):303–314, 1989\.
  * DJ [98] David L Donoho and Iain M Johnstone.  Minimax estimation via wavelet shrinkage.  The annals of Statistics, 26(3):879–921, 1998.
  * DJ [02] Robert M De Jong.  A note on “convergence rates and asymptotic normality for series estimators”: uniform convergence rates.  Journal of Econometrics, 111(1):1–9, 2002.
  * FLM [21] Max H Farrell, Tengyuan Liang, and Sanjog Misra.  Deep neural networks for estimation and inference.  Econometrica, 89(1):181–213, 2021.
  * FZT [18] Farzan Farnia, Jesse Zhang, and David Tse.  Generalizable adversarial training via spectral normalization.  In International Conference on Learning Representations, 2018.
  * GKS [04] Evarist Giné, Vladimir Koltchinskii, and Lyudmila Sakhanenko.  Kernel density estimators: convergence in distribution for weighted sup-norms.  Probability Theory and Related Fields, 130(2):167–198, 2004.
  * GN [09] Evarist Giné and Richard Nickl.  Uniform limit theorems for wavelet density estimators.  The Annals of Probability, 37(4):1605–1646, 2009.
  * GN [11] Evarist Giné and Richard Nickl.  Rates of contraction for posterior distributions in lr-metrics, 1$\leq$ r$\leq\infty$.  The Annals of Statistics, 39(6):2883–2911, 2011.
  * GN [21] Evarist Giné and Richard Nickl.  Mathematical foundations of infinite-dimensional statistical models.  Cambridge university press, 2021.
  * GS [13] Evarist Giné and Hailin Sang.  On the estimation of smooth densities by strict probability densities at optimal rates in sup-norm.  IMS Collections, From Probability to Statistics and Back: High-Dimensional Models and Processes, 9:128–149, 2013.
  * GSS [14] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:1412.6572, 2014.
  * HJ [22] Hamed Hassani and Adel Javanmard.  The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression.  arXiv preprint arXiv:2201.05149, 2022.
  * HJS [88] W Hardle, Paul Janssen, and Robert Serfling.  Strong uniform consistency rates for estimators of conditional functionals.  The Annals of Statistics, pages 1428–1449, 1988.
  * HLM [17] Nick Harvey, Christopher Liaw, and Abbas Mehrabian.  Nearly-tight vc-dimension bounds for piecewise linear neural networks.  In Conference on learning theory, pages 1064–1068. PMLR, 2017.
  * HRSH [15] Marc Hoffmann, Judith Rousseau, and Johannes Schmidt-Hieber.  On adaptive posterior concentration rates.  The Annals of Statistics, 43(5):2259–2295, 2015.
  * HZRS [16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * IF [19] Masaaki Imaizumi and Kenji Fukumizu.  Deep neural networks learn non-smooth functions effectively.  In The 22nd international conference on artificial intelligence and statistics, pages 869–878. PMLR, 2019.
  * IF [22] Masaaki Imaizumi and Kenji Fukumizu.  Advantage of deep neural networks for estimating functions with singularity on hypersurfaces.  Journal of Machine Learning Research, 23:1–54, 2022.
  * Jia [19] Heinrich Jiang.  Non-asymptotic uniform rates of consistency for k-nn regression.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3999–4006, 2019.
  * JSH [20] Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani.  Precise tradeoffs in adversarial training for linear regression.  In Conference on Learning Theory, pages 2034–2078. PMLR, 2020.
  * JSLH [21] Yuling Jiao, Guohao Shen, Yuanyuan Lin, and Jian Huang.  Deep nonparametric regression on approximately low-dimensional manifolds.  arXiv preprint arXiv:2104.06708, 2021.
  * KGB [16] Alexey Kurakin, Ian Goodfellow, and Samy Bengio.  Adversarial machine learning at scale.  arXiv preprint arXiv:1611.01236, 2016.
  * KL [18] Justin Khim and Po-Ling Loh.  Adversarial risk bounds via function transformation.  arXiv preprint arXiv:1810.09519, 2018.
  * KL [21] Michael Kohler and Sophie Langer.  On the rate of convergence of fully connected deep neural network regression estimates.  The Annals of Statistics, 49(4):2231–2249, 2021.
  * KSH [17] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Communications of the ACM, 60(6):84–90, 2017.
  * KT [12] Aleksandr Petrovich Korostelev and Alexandre B Tsybakov.  Minimax theory of image reconstruction, volume 82.  Springer Science & Business Media, 2012.
  * Lab [97] DA Labutin.  Integral representations of functions and embeddings of sobolev spaces on cuspidal domains.  Mathematical Notes, 61:164–179, 1997.
  * LBH [15] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  nature, 521(7553):436–444, 2015.
  * LLPS [93] Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken.  Multilayer feedforward networks with a nonpolynomial activation function can approximate any function.  Neural networks, 6(6):861–867, 1993.
  * LPW+ [17] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang.  The expressive power of neural networks: A view from the width.  Advances in neural information processing systems, 30, 2017.
  * LSYZ [21] Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang.  Deep network approximation for smooth functions.  SIAM Journal on Mathematical Analysis, 53(5):5465–5506, 2021.
  * Mas [00] Elias Masry.  Wavelet-based estimation of multivariate regression functions in besov spaces.  Journal of Nonparametric Statistics, 12(2):283–308, 2000.
  * MHS [19] Omar Montasser, Steve Hanneke, and Nathan Srebro.  Vc classes are adversarially robustly learnable, but only improperly.  In Conference on Learning Theory, pages 2512–2530. PMLR, 2019.
  * MJR+ [21] Mohammad Mehrabi, Adel Javanmard, Ryan A Rossi, Anup Rao, and Tung Mai.  Fundamental tradeoffs in distributionally adversarial training.  In International Conference on Machine Learning, pages 7544–7554. PMLR, 2021.
  * MMS+ [18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In International Conference on Learning Representations, 2018.
  * New [97] Whitney K Newey.  Convergence rates and asymptotic normality for series estimators.  Journal of econometrics, 79(1):147–168, 1997.
  * NI [20] Ryumei Nakada and Masaaki Imaizumi.  Adaptive approximation and generalization of deep neural network with intrinsic dimensionality.  J. Mach. Learn. Res., 21(174):1–38, 2020.
  * Par [62] Emanuel Parzen.  On estimation of a probability density function and mode.  The annals of mathematical statistics, 33(3):1065–1076, 1962.
  * Pee [76] Jack Peetre.  New thoughts on besov spaces, duke univ.  Math. Ser, 1:45–55, 1976.
  * PMW+ [16] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami.  Distillation as a defense to adversarial perturbations against deep neural networks.  In 2016 IEEE symposium on security and privacy (SP), pages 582–597. IEEE, 2016.
  * RKH [20] Kevin Roth, Yannic Kilcher, and Thomas Hofmann.  Adversarial training is a form of data-dependent operator norm regularization.  Advances in Neural Information Processing Systems, 33:14973–14985, 2020.
  * RS [22] Antônio H Ribeiro and Thomas B Schön.  Overparameterized linear regression under adversarial attacks.  arXiv preprint arXiv:2204.06274, 2022.
  * Sch [07] Larry Schumaker.  Spline functions: basic theory.  Cambridge university press, 2007.
  * SH [19] Johannes Schmidt-Hieber.  Deep relu network approximation of functions on a manifold.  arXiv preprint arXiv:1908.00695, 2019.
  * SH [20] Johannes Schmidt-Hieber.  Nonparametric regression using deep neural networks with relu activation function.  The Annals of Statistics, 48(4):1875–1897, 2020.
  * SHZ [22] Johannes Schmidt-Hieber and Petr Zamolodtchikov.  Local convergence rates of the least squares estimator with applications to transfer learning.  arXiv preprint arXiv:2204.05003, 2022.
  * Sil [78] Bernard W Silverman.  Weak and strong uniform consistency of the kernel estimate of a density and its derivatives.  The Annals of Statistics, pages 177–184, 1978.
  * SJL+ [21] Guohao Shen, Yuling Jiao, Yuanyuan Lin, Joel L. Horowitz, and Jian Huang.  Deep quantile regression: Mitigating the curse of dimensionality through composition.  arXiv preprint arXiv:2107.04907, 2021.
  * SJLH [21] Guohao Shen, Yuling Jiao, Yuanyuan Lin, and Jian Huang.  Robust nonparametric regression with deep neural networks.  arXiv preprint arXiv:2107.10343, 2021.
  * SN [21] Taiji Suzuki and Atsushi Nitanda.  Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic besov space.  Advances in Neural Information Processing Systems, 34:3609–3621, 2021.
  * Son [08] Kyungchul Song.  Uniform convergence of series estimators over function spaces.  Econometric Theory, 24(6):1463–1499, 2008.
  * SST+ [18] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry.  Adversarially robust generalization requires more data.  Advances in neural information processing systems, 31, 2018.
  * Sto [80] Charles J Stone.  Optimal rates of convergence for nonparametric estimators.  The annals of Statistics, pages 1348–1360, 1980.
  * Sto [82] Charles J Stone.  Optimal global rates of convergence for nonparametric regression.  The annals of statistics, pages 1040–1053, 1982.
  * Suz [18] Taiji Suzuki.  Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality.  arXiv preprint arXiv:1810.08033, 2018.
  * TPG+ [17] Florian Tramèr, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel.  The space of transferable adversarial examples.  arXiv preprint arXiv:1704.03453, 2017.
  * TS [21] Kazuma Tsuji and Taiji Suzuki.  Estimation error analysis of deep learning on the regression problem on the variable exponent besov space.  Electronic Journal of Statistics, 15(1):1869–1908, 2021.
  * Tsy [08] Alexandre B Tsybakov.  Introduction to nonparametric estimation.  Springer Science & Business Media, 2008.
  * VSP+ [17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * VW [96] Aad W Vaart and Jon A Wellner.  Weak convergence.  In Weak convergence and empirical processes, pages 16–28. Springer, 1996.
  * WMB+ [21] Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu.  On the convergence and robustness of adversarial training.  arXiv preprint arXiv:2112.08304, 2021.
  * WZY+ [19] Yisen Wang, Difan Zou, Jinfeng Yi, James Bailey, Xingjun Ma, and Quanquan Gu.  Improving adversarial robustness requires revisiting misclassified examples.  In International Conference on Learning Representations, 2019.
  * YBP [17] Yun Yang, Anirban Bhattacharya, and Debdeep Pati.  Frequentist coverage and sup-norm convergence rate in gaussian process regression.  arXiv preprint arXiv:1708.04753, 2017.
  * YG [16] William Weimin Yoo and Subhashis Ghosal.  Supremum norm posterior contraction and credible sets for nonparametric multivariate regression.  The Annals of Statistics, 44(3):1069–1102, 2016.
  * YKB [19] Dong Yin, Ramchandran Kannan, and Peter Bartlett.  Rademacher complexity for adversarially robust generalization.  In International conference on machine learning, pages 7085–7094. PMLR, 2019.
  * ZCH+ [19] Runtian Zhai, Tianle Cai, Di He, Chen Dan, Kun He, John Hopcroft, and Liwei Wang.  Adversarially robust generalization just requires more unlabeled data.  arXiv preprint arXiv:1906.00555, 2019.
  * ZWZ [02] Shuanglin Zhang, Man-Yu Wong, and Zhongguo Zheng.  Wavelet threshold estimation of a regression function with random design.  Journal of multivariate analysis, 80(2):256–284, 2002.
  * ZYJ+ [19] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan.  Theoretically principled trade-off between robustness and accuracy.  In International conference on machine learning, pages 7472–7482. PMLR, 2019.