The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
88,890 characters
Phase transitions in nonparametric regressions
\title{Phase transitions in nonparametric regressions\thanks{Keywords: Phase transition; smooth functions; covering and packing
numbers; minimax optimality; nonparametric regressions}}
\author{Ying Zhu\\
First draft on arXiv: December 7, 2021. This draft: October 4, 2023\thanks{Assistant Professor of Economics at UC San Diego. [email removed].
I thank the co-editor Elie Tamer, the anonymous AE and two anonymous
referees for their valuable comments. I would also like to thank Xiaohong
Chen, Fang Han, Hidehiko Ichimura, Oliver Linton and Yixiao Sun for
substantial comments. I am also grateful to Don Andrews, Matias Cattaneo,
Julie Cullen, Bo Honor�, Michael Jansson, Jason Klusowski, Shakeeb
Khan, Esfandiar Maasoumi, Ulrich M�ller, Mikkel Plagborg-Moller, Dimitris
Politis, Chris Sims, and Zhijie Xiao. I am thankful to the Society
of Hellman Fellows at University of California and the Cowles Foundation
at Yale University, and appreciate everyone who attended my talks
at a number of seminars and conferences.}}
\maketitle
\begin{abstract}
When the unknown regression function of a single variable is known
to have derivatives up to the $(\gamma+1)$th order bounded in absolute
values by a common constant everywhere or a.e. (i.e., $(\gamma+1)$th
degree of smoothness), the minimax optimal rate of the mean integrated
squared error (MISE) is stated as $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
in the literature. This paper shows that: (i) if $n\leq\left(\gamma+1\right)^{2\gamma+3}$,
the minimax optimal MISE rate is $\frac{\log n}{n\log(\log n)}$ and
the optimal degree of smoothness to exploit is roughly $\max\left\{ \left\lfloor \frac{\log n}{2\log\left(\log n\right)}\right\rfloor ,\,1\right\} $;
(ii) if $n>\left(\gamma+1\right)^{2\gamma+3}$, the minimax optimal
MISE rate is $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
and the optimal degree of smoothness to exploit is $\gamma+1$.
The fundamental contribution of this paper is a set of metric entropy
bounds we develop for smooth function classes. Some of our bounds
are original, and some of them improve and/or generalize the ones
in the literature (e.g., Kolmogorov and Tikhomirov, 1959). Our metric
entropy bounds allow us to show phase transitions in the minimax optimal
MISE rates associated with some commonly seen smoothness classes as
well as non-standard smoothness classes, and can also be of independent
interest outside the nonparametric regression problems.\\
\\
\end{abstract}
\section{Introduction\label{sec:Introduction}}
Estimation of an unknown univariate function $f$ from the nonparametric
regression model
\begin{equation}
Y_{i}=f(X_{i})+\varepsilon_{i},\,i=1,...,n\label{eq:model}
\end{equation}
has been a central research topic in econometrics, machine learning,
numerical analysis and statistics. Many semiparametric estimators
involve nonparametric regressions as an intermediate step, and some
of the classical examples in economics can be found in several \textit{Handbook
of Econometrics} chapters such as Powell (1994), Chen (2007), and
Ichimura and Todd (2007). The typical assumption about $f$ in (\ref{eq:model})
is that it has derivatives up to a given $(\gamma+1)$th order bounded
in absolute values by a common constant everywhere or almost everywhere
(a.e.). Given an estimator of $f$, an important object of interest
is the convergence rate of the mean integrated squared error (MISE)
of this estimator and the minimax optimality property of the MISE
rate, which tells one how fast the population mean squared distance
between the estimator and $f$ shrinks to zero uniformly when $f$
ranges over a smoothness class, as the sample size $n$ increases.
In particular, MISE is a global mean squared error criterion by integrating
over all possible values of the covariate and noise with respect to
some underlying distribution (see Pagan and Ullah, 1999).
When the smoothness degree $\gamma+1$ is finite and the sample size
$n\rightarrow\infty$, existing \textit{asymptotic} results show that
the minimax optimal MISE rate is $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
which decreases as $\gamma+1$ increases. In the literature of statistical
learning theory, $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
is also stated as the \textit{nonasymptotic} minimax optimal rate
and derived without assuming $n\rightarrow\infty$. See Tsybakov (2009)
for a comprehensive review of the literature that show the classical
asymptotic minimax optimal rate $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
under the assumption of $\gamma+1$ being finite and $n$ tending
to infinity. See Wainwright (2019) for the nonasymptotic derivation.
The rate $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
gives arise to the so called ``blessing of smoothness'' folklore
(i.e., the more smoothness one can exploit, the better) in the theoretical
community.
In terms of the minimax optimal MISE rates associated with the \textit{standard}
$(\gamma+1)$th degree smoothness classes\footnote{In this paper, a \textit{standard} $(\gamma+1)$th degree smoothness
class refers to one that consists of functions with derivatives belonging
to a ball of some constant radius independent of the derivative order
and bounded away from zero and from above, with respect to either
an $l_{\infty}$ (max) norm or a Hilbert norm.}, we show the following results: (i) if $n\leq\left(\gamma+1\right)^{2\gamma+3}$
(the ``small $n$'' regime), the minimax optimal MISE rate is $\frac{\log n}{n\log(\log n)}$
and the optimal degree of smoothness to exploit is roughly $\max\left\{ \left\lfloor \frac{\log n}{2\log\left(\log n\right)}\right\rfloor ,\,1\right\} $;\footnote{``$\log$'' in this paper is natural logarithm. The more precise
characterization of the optimal degree of smoothness to exploit under
$n\leq\left(\gamma+1\right)^{2\gamma+3}$ is detailed in Section \ref{sec:Minimax-standard}.} (ii) if $n>\left(\gamma+1\right)^{2\gamma+3}$ (the ``large $n$''
regime, which clearly includes the case of $\gamma$ being finite
and $n$ tending to infinity), the minimax optimal MISE rate is $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
and the optimal degree of smoothness to exploit is $\gamma+1$. To
our knowledge, this paper is the first in the literature to show the
minimax optimal rate in the ``small $n$'' regime and the sample
size (i.e., $\left(\gamma+1\right)^{2\gamma+3}$) at which the minimax
optimal rate transitions from $\frac{\log n}{n\log(\log n)}$ to $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$.
The definition of our minimax optimal rates is based on the existing
literature. A rate is said to be minimax optimal in our problem if
we can show: (1) the MISE for \textit{any} estimators (by taking the
infimum over all estimators) in the worst case scenario (by taking
the supremum over a $(\gamma+1)$th degree smoothness class) is bounded
from below, and such a bound is called a minimax lower bound; (2)
there exists an estimator such that its MISE in the worst case scenario
has an upper bound that matches the lower bound in terms of the rate,
the so-called achievability result; to be precise, apart from some
universal constant independent of $n$ (and in our interest, also
independent of $\gamma$), the upper bound matches the lower bound
and the matching part is the minimax optimal rate. The difference
in the ``constants'' between our results and the existing literature
is that the constants in our bounds are truly \textit{universal constants
that are independent of $n$ and $\gamma$ and bounded away from zero
and from above}, while those in the existing literature cannot be
independent of $\gamma$. This difference allows us to provide an
asymptotic interpretation for the rate $\frac{\log n}{n\log(\log n)}$
in the ``small $n$'' regime (in Section \ref{sec:Minimax-standard})
relative to the classical rate $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$:
\begin{itemize}
\item as $n\rightarrow\infty$ and $\left(\gamma+1\right)^{2\gamma+3}\rightarrow\infty$,
while
\begin{equation}
n=o\left(\left(\gamma+1\right)^{2\gamma+3}\right),\label{eq:asymptotic condition}
\end{equation}
then
\begin{equation}
\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}=o\left(\frac{\log n}{n\log(\log n)}\right);\label{eq:asymptotic interpretation}
\end{equation}
\item as $n\rightarrow\infty$ and $\left(\gamma+1\right)^{2\gamma+3}\rightarrow\infty$,
while
\begin{equation}
\left(\gamma+1\right)^{2\gamma+3}=o(n),\label{eq:asymptotic condition_1}
\end{equation}
then
\[
\frac{\log n}{n\log(\log n)}=o\left(\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}\right);
\]
that is, the rate $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
kicks in.\footnote{It is worth pointing out that the results in Section \ref{sec:Minimax-standard}
hold both non-asymptotically and asymptotically. One may interpret
the results in Section \ref{sec:Minimax-standard} in the context
of a triangular data generating process where the smoothness degree
is indexed by the sample size. }
\end{itemize}
Particularly, we show in this paper that, if the maximum smoothness
degree of $f$ is $\gamma+1$, estimators which minimize the sum of
squared residuals and are constrained to exploit the optimal degree
of smoothness achieve the abovementioned minimax optimal MISE rates.
These estimators will be referred to as the constrained nonparametric
least squares estimator (CNLS) in the following. CNLS estimators constrained
to be in a Sobolev class associated with a Reproducing Kernel Hilbert
Space (RKHS) radius have nice closed form expressions via kernel functions
and are easy to implement in the regularized form, often referred
to as the kernel ridge regression (KRR) estimators (among the most
popular nonparametric estimators) in machine learning. There is a
rich theory based on RKHS for the asymptotic properties of such estimators
under the regime where $\gamma+1$ is finite and $n\rightarrow\infty$
(see, e.g., Sch�lkopf and Smola, 2002; Berlinet and Thomas-Agnan,
2004). These estimators are closely related to smoothing splines methods
and Gaussian process regressions (see, Wahba, 1990; Rasmussen and
Williams, 2006).
It is worth mentioning the connection between our theoretical results
and some numerical findings from the literature. From a practical
view-point, Marron and Wand (1992) find the exact MISE of kernel density
estimators based on Gaussian kernels can increase with the order of
kernel being exploited (the assumed degree of smoothness) when the
sample size is moderate. Marron (1994) further shows in simulations
that the second order kernel produces a smaller MISE than the fourth
order kernel when the sample size is between $70$ and $10000$, and
the fourth order kernel is dominantly better than the second order
kernel when $n>10000$. Despite that our focus in this paper is on
the minimax optimal rates and our achievability results concern global
nonparametric procedures such as KRR (instead of kernel density estimators
based on Gaussian kernels), Marron and Wand (1992) and our paper share
one general message: the classical rate $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
is an underestimate of the MISE when $n$ is not large enough. Another
message conveyed by our paper is that the optimal degree of smoothness
to exploit should depend on the sample size.
In econometrics, there is increasing empirical evidence against exploiting
higher degrees of smoothness. Graham, et. al (2010) comment, ``As
is usual in semiparametric estimation, higher order kernels are required
for bias reduction, although the use of such kernels in practice may
be ill-advised.'' Based on several empirical studies with sample
sizes ranging from a couple of thousands to at most thirties of thousands,
Gelman and Imbens (2019) recommend researchers to avoid using high
order polynomials but use local linear or local quadratic polynomials
to estimate the two conditional mean functions of a pretreatment variable
in regression discontinuity designs (RDD) analyses.
The implication of our results extends to other applications. Establishing
the convergence rate of a semiparametric procedure often requires
establishing an MISE rate or its sample analogue concerning a first-step
nonparametric regression. Below are a couple of examples:
\begin{itemize}
\item When applying a 2SLS-type procedure to estimate a triangular system
where the first-stage equations linking the endogenous regressors
with instruments take the form of (\ref{eq:model}), the MSE of the
2SLS estimator for the parameters of interest in the second-stage
(main) equation depends on the MISE of the first-stage estimators.
\item When applying the partialling-out type strategy to estimate the parameters
of interest in a partially linear model, the first step uses a nonparametric
regression to obtain the partial residuals, and the second step uses
a least squares procedure or a regularized least squares procedure
based on the estimated residuals from the first step. The MSE of the
second step estimator depends on the MISE of the first-step estimator.\footnote{For the partially linear models in Item 2, following derivations similar
to those in Zhu (2017) would reveal the dependence. For the triangular
systems in Item 1, following derivations similar to those in Zhu (2018)
would reveal the dependence; in particular, the modifications involve
replacing terms like $\left(Z_{ij}\hat{\pi}_{j}-Z_{ij}\pi_{j}^{*}\right)^{2}$
in Zhu (2018) with $\left(\hat{f}\left(Z_{ij}\right)-f\left(Z_{ij}\right)\right)^{2}$,
where $j$ is the index of the endogenous variables and $Z_{ij}$
is an instrumental variable for the $j$th endogenous variable.}
\end{itemize}
\section{Overview of our results}
\subsection{Preliminaries }
\textbf{Notation}. Let $\left\lfloor x\right\rfloor $ denote the
largest integer smaller than or equal to $x$. For two functions $f(n,\gamma)$
and $g(n,\gamma)$, let us write $f(n,\gamma)\succsim g(n,\gamma)$
if $f(n,\gamma)\geq cg(n,\gamma)$ for a universal constant $c\in(0,\,\infty)$;
similarly, we write $f(n,\gamma)\precsim g(n,\gamma)$ if $f(n,\gamma)\leq c^{'}g(n,\gamma)$
for a universal constant $c^{'}\in(0,\,\infty)$; and $f(n,\gamma)\asymp g(n,\gamma)$
if $f(n,\gamma)\succsim g(n,\gamma)$ and $f(n,\gamma)\precsim g(n,\gamma)$.
Throughout this paper, we use various $c$ and $C$ letters to denote
positive universal constants that are: finite and bounded away from
zero (denoted by $\asymp1$) and independent of $n$ and $\gamma$
and the dimension $d$ of the covariates (when $d-$dimensional covariates
are of interest); these constants may vary from place to place.
For a $J-$dimensional vector $\theta$, the $l_{q}-$norm $\left|\theta\right|{}_{q}:=\left(\sum_{j=1}^{J}|\theta_{j}|^{q}\right)^{1/q}$
if $1\leq q<\infty$ and $\left|\theta\right|{}_{q}:=\max_{j\in\left\{ 1,...,J\right\} }\left|\theta_{j}\right|$
if $q=\infty$. Let $\mathbb{B}_{q}^{J}\left(R\right):=\left\{ \theta\in\mathbb{R}^{J}:\left|\theta\right|_{q}\leq R\right\} $.
For functions on $\left[a,\,b\right]$, the unweighted $L^{2}-$norm
$\left|f-g\right|_{2}:=\sqrt{\int_{a}^{b}\left[f\left(x\right)-g\left(x\right)\right]^{2}dx}$,
and the weighted $L^{2}\left(\mathbb{P}\right)-$norm $\left|f-g\right|_{2,\mathbb{P}}:=\sqrt{\int_{a}^{b}\left[f\left(x\right)-g\left(x\right)\right]^{2}\mathbb{P}(dx)}$.
For functions on $\left[a,\,b\right]^{d}$, the supremum norm $\left|f-g\right|_{\infty}:=\sup_{x\in\left[a,\,b\right]^{d}}\left|f\left(x\right)-g\left(x\right)\right|$.
Finally, the $\mathcal{L}^{2}(\mathbb{P}_{n})-$norm of the vector
$f:=\left\{ f(x_{i})\right\} _{i=1}^{n}$, denoted by $\left|f\right|_{n}$,
is $\left[\frac{1}{n}\sum_{i=1}^{n}\left(f(x_{i})\right)^{2}\right]^{\frac{1}{2}}$.
\subsubsection{Classes of smooth functions\label{subsec:Classes-of-smooth}}
\begin{definition}[Generalized H�lder subclass] For a non-negative
integer $\gamma$, we let the H�lder\textit{ class} $\mathcal{U}_{\gamma+1}\left(\left(R_{k}\right)_{k=0}^{\gamma+1},\,\left[-1,\,1\right]\right)$
be the class of functions such that any function $f\in\mathcal{U}_{\gamma+1}\left(\left(R_{k}\right)_{k=0}^{\gamma+1},\,\left[-1,\,1\right]\right)$
satisfies: (1) $f$ is continuous on $\left[-1,\,1\right]$ and all
derivatives of $f$ exist; (2) $\left|f^{k}\left(x\right)\right|\leq R_{k}$
for all $k=0,...,\gamma$ and $x\in\left[-1,\,1\right]$, where $f^{0}\left(x\right)=f\left(x\right)$;
(3) $\left|f^{\gamma}(x)-f^{\gamma}(x^{'})\right|\leq R_{\gamma+1}\left|x-x^{'}\right|$
for all $x,\,x^{'}\in\left[-1,\,1\right]$.
\end{definition}
\begin{remark} Note that in our definition of $\mathcal{U}_{\gamma+1}$,
the absolute values of the derivatives of any member are allowed to
depend on the derivative order. This is motivated by nonparametric
procedures for recovering solutions of ordinary differential equations
in the literature of functional data analysis. We refer interested
readers to Zhu and Mirzaei (2021) for the details.
\end{remark}
Any function $f$ in a H�lder class on $\left[-1,\,1\right]$ can
be written as
\begin{equation}
f(x)=\underset{poly}{\underbrace{\sum_{k=0}^{\gamma}\frac{x^{k}}{k!}f^{(k)}(0)}}+\frac{x^{\gamma}}{\gamma!}f^{(\gamma)}(z)-\frac{x^{\gamma}}{\gamma!}f^{(\gamma)}(0)\label{eq:expansion}
\end{equation}
where $z$ is some intermediate value between $x$ and $0$, and we
follow the convention $0^{0}=0!=1$.
\begin{definition}[Generalized polynomial subclass] The \textit{generalized
polynomial subclass consisting of functions in the form of ``$poly$''
in (\ref{eq:expansion}) can be expressed as}
\[
\mathcal{U}_{\gamma+1,1}=\left\{ f(x)=\sum_{k=0}^{\gamma}\theta_{k}x^{k}:\textrm{\ensuremath{\left(\theta_{k}\right)_{k=0}^{\gamma}}\ensuremath{\ensuremath{\in}}\ensuremath{\mathcal{P}_{\gamma}}},\,x\in\left[-1,\,1\right]\right\}
\]
with the $\left(\gamma+1\right)-$dimensional polyhedron
\[
\ensuremath{\mathcal{P}_{\gamma}=\left\{ \ensuremath{\left(\theta_{k}\right)_{k=0}^{\gamma}}\ensuremath{\ensuremath{\in}}\mathbb{R}^{\gamma+1}:\theta_{k}\in\left[\frac{-R_{k}}{k!},\,\frac{R_{k}}{k!}\right]\right\} }.
\]
\end{definition}
\begin{definition}[Generalized H�lder subclass] The \textit{generalized
H�lder subclass} $\mathcal{U}_{\gamma+1,2}$ is the class of functions
such that any function $f\in\mathcal{U}_{\gamma+1,2}$ satisfies:
$f\in\mathcal{U}_{\gamma+1}$ such that $f^{(k)}\left(0\right)=0$
for all $k=0,...,\gamma$.
\end{definition}
Consequently, we have the following relationships:
\begin{eqnarray}
& \mathcal{U}_{\gamma+1,1}\subseteq\mathcal{U}_{\gamma+1}, & \mathcal{U}_{\gamma+1,2}\subseteq\mathcal{U}_{\gamma+1},\label{eq:inner}\\
\mathcal{U}_{\gamma+1}\subseteq & \mathcal{U}_{\gamma+1,1}+\mathcal{U}_{\gamma+1,2} & :=\left\{ f_{1}+f_{2}:f_{1}\in\mathcal{U}_{\gamma+1,1},\,f_{2}\in\mathcal{U}_{\gamma+1,2}\right\} .\label{eq:outter}
\end{eqnarray}
As discussed in Wainwright (2019, Chapter 12), any function $f$ in
the Sobolev space on $\left[0,\,1\right]$ has the expansion
\[
f\left(x\right)=\sum_{k=0}^{\gamma}f^{(k)}(0)\frac{x^{k}}{k!}+\int_{0}^{1}f^{(\gamma+1)}(t)\frac{\left(x-t\right)_{+}^{\gamma}}{\gamma!}dt\quad\textrm{with }(a)_{+}=a\vee0,
\]
and one (RK)HS norm associated with a Sobolev space takes the form
\begin{equation}
\left|f\right|_{\mathcal{H},\gamma+1}=\sqrt{\sum_{k=0}^{\gamma}\left(f^{(k)}(0)\right)^{2}+\int_{0}^{1}\left[f^{(\gamma+1)}\left(t\right)\right]^{2}dt}.\label{eq:sobolev norm}
\end{equation}
Therefore, the Sobolev space can be decomposed into a polynomial subspace
and a Sobolev subspace imposed with the restrictions that $f^{(k)}(0)=0$
for all $k=0,...,\gamma$ and $f^{(\gamma+1)}$ belongs to the space
$\mathcal{L}^{2}\left[0,\,1\right]$ (see Wahba, 1990, Chapter 1;
Wainwright, 2019, Chapter 12, Examples 12.17 and 12.29). A Sobolev
subclass is a special case of the ellipsoid subclass; in particular,
a Sobolev subclass can be expressed in the following way (Wainwright
2019, Chapters 5, 12 and 15).
\begin{definition}[Generalized ellipsoid subclass] The \textit{generalized
ellipsoid subclass} of smooth functions
\begin{equation}
\mathcal{H}_{\gamma+1}=\left\{ f=\sum_{m=1}^{\infty}\theta_{m}\phi_{m}:\textrm{for }\left(\theta_{m}\right)_{m=1}^{\infty}\ensuremath{\in}\ell^{2}\left(\mathbb{N}\right)\textrm{ such that }\sum_{m=1}^{\infty}\frac{\theta_{m}^{2}}{\mu_{m}}\leq R_{\gamma+1}^{2}\right\} \label{eq:Ellipsoid-1}
\end{equation}
where $\ell^{2}\left(\mathbb{N}\right):=\left\{ \left(\theta_{m}\right)_{m=1}^{\infty}\vert\sum_{m=1}^{\infty}\theta_{m}^{2}<\infty\right\} $,
$\left(\mu_{m}\right)_{m=1}^{\infty}$ and $\left(\phi_{m}\right)_{m=1}^{\infty}$
are the eigenvalues and eigenfunctions (that forms an orthonormal
basis of $\mathcal{L}^{2}\left[0,\,1\right]$), respectively, of an
RKHS associated with a continuous and semidefinite kernel function.
\end{definition}
When considering $\mathcal{H}_{\gamma+1}$ in (\ref{eq:Ellipsoid-1}),
we will assume that $\mu_{m}=\left(cm\right)^{-2\left(\gamma+1\right)}$
for a positive constant $c\asymp1$ independent of $\gamma$ and $R_{\gamma+1}$.
The decay rate of the eigenvalues follows the standard assumption
for $(\gamma+1)-$degree smooth functions in the literature (see,
e.g., Steinwart and Christmann, 2008; Wainwright, 2019) and $R_{\gamma+1}\asymp1$
in (\ref{eq:Ellipsoid-1}) gives the \textit{standard} ellipsoid subclass.
Moreover, (\ref{eq:Ellipsoid-1}) is equipped with the inner product
$\left\langle h,\,g\right\rangle _{\mathcal{H}}=\sum_{m=1}^{\infty}\frac{\left\langle h,\,\phi_{m}\right\rangle \left\langle g,\,\phi_{m}\right\rangle }{\mu_{m}}$
where $\left\langle \cdot,\cdot\right\rangle $ is the inner product
in $\mathcal{L}^{2}\left[0,\,1\right]$.
\subsubsection{Metric entropy}
\begin{definition}[Covering and packing numbers]
Given a set $\Lambda$, a set $\left\{ \mathrm{\eta}^{1},\,\mathrm{\eta}^{2},...,\mathrm{\eta}^{N}\right\} \subset\Lambda$
is a $\delta-$cover of $\Lambda$ in the metric $\rho$ if for each
$\eta\in\Lambda$, there exists some $i\in\left\{ 1,...,N\right\} $
such that $\rho(\eta,\,\eta^{i})\leq\delta$. The $\delta-$covering
number of $\Lambda$, denoted by $N_{\rho}(\delta,\,\Lambda)$, is
the cardinality of the smallest $\delta-$cover. A set $\left\{ \mathrm{\eta}^{1},\,\mathrm{\eta}^{2},...,\mathrm{\eta}^{M}\right\} \subset\Lambda$
is a $\delta-$packing of $\Lambda$ in the metric $\rho$ if for
any distinct $i,j\in\left\{ 1,...,M\right\} $, $\rho(\eta^{i},\,\eta^{j})>\delta$.
The $\delta-$packing number of $\Lambda$, denoted by $M_{\rho}(\delta,\,\Lambda)$,
is the cardinality of the largest $\delta-$packing. Throughout this
paper, we use $N_{q}\left(\delta,\,\mathcal{\mathcal{F}}\right)$
and $M_{q}\left(\delta,\,\mathcal{\mathcal{F}}\right)$ to denote
the $\delta-$covering number and the $\delta-$packing number, respectively,
of a function class $\mathcal{F}$ with respect to the function norm
$\left|\cdot\right|_{q}$ where $q\in\left\{ 2,\,\infty\right\} $;
moreover, $N_{2,\mathbb{P}}\left(\delta,\,\mathcal{\mathcal{F}}\right)$
and $M_{2,\mathbb{P}}\left(\delta,\,\mathcal{\mathcal{F}}\right)$
denote the $\delta-$covering number and the $\delta-$packing number,
respectively, of a function class $\mathcal{F}$ with respect to the
weighted $L^{2}\left(\mathbb{P}\right)-$norm $\left|\cdot\right|_{2,\mathbb{P}}$.
\end{definition}
The following is a standard textbook result that summarizes the relationships
between covering and packing numbers:
\begin{equation}
M_{\rho}(2\delta,\,\Lambda)\leq N_{\rho}(\delta,\,\Lambda)\leq M_{\rho}(\delta,\,\Lambda).\label{eq:sandwich}
\end{equation}
Given this sandwich result, a lower bound on the packing number gives
a lower bound on the covering number, and vice versa; similarly, an
upper bound on the covering number gives an upper bound on the packing
number, and vice versa.
Metric entropy is an important concept in approximation theory and
discrete geometry. In mathematical statistics and machine learning
theory, metric entropy is a fundamental building block. Combined with
the Fano's inequality from information theory (see, Cover and Thomas,
2005), it allows one to derive the minimax lower bounds for the MISE
rates; combined with the notion of ``local complexity'' in empirical
processes theory, it allows one to derive upper bounds on the MISE
rates.\footnote{For the \textit{standard} smoothness classes, one may use methods
based on ``ranks'' (for the polynomial subclass) and ``eigenvalues''
(for the nonparametric subclass) to derive upper bounds on the MISE.
However, ``ranks'' are not very useful for deriving the minimax
lower bounds in general. Even for upper bounds in the case of a H�lder
class, once we allow $R_{k}$ to depend on the order of derivative,
$k$, the ``rank''--based argument is hard to generalize as it
does not account for the impact of $R_{k}$.}
\subsection{Our contributions\label{subsec:Our-contributions}}
In the existing literature, the minimax lower bound and the upper
bound (for achievability) for MISE is typically stated as $\mathtt{constant}\cdot\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
and $\mathtt{constant'}\cdot\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$,
respectively, where the specific forms of $\mathtt{constant}$ and
$\mathtt{constant}'$ are not derived. Then the matching part ``$\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$''
is claimed as the minimax optimal rate (e.g., Wainwright, 2019). Deriving
constants for global criteria such as MISE and demonstrating achievability
(upper bounds) in the context of global nonparametric procedures (the
focus of our paper) is known to be difficult, which is why the existing
literature does not make an attempt in deriving the constants.
Relative to the existing literature, our results take one step further
by revealing more explicit dependence on $n$, $\gamma$ and $\left\{ R_{k}\right\} _{k=0}^{\gamma+1}$.
The difference in the ``constants'' between our results and the
existing literature is that the constants in our bounds are truly
\textit{universal} constants that are independent of $n$ and $\gamma$
and bounded away from zero and from above, while those in the existing
literature cannot be independent of $\gamma$, as explained in the
next section. This difference allows us to provide an asymptotic interpretation
for the rate $\frac{\log n}{n\log(\log n)}$ in the ``small $n$''
regime (in Section \ref{sec:Minimax-standard}) relative to the classical
rate $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$, as
discussed in Section \ref{sec:Introduction}.\footnote{Because of the complexity of our problems, we make no attempt to derive
the explicit universal constants that are \textit{independent} of
$n$ and $\gamma$. The following process is a standard one used in
this literature for proving minimax optimal rates in MISE and explains
why such a derivation is not carried out: First, results on metric
entropy are derived. Then, these results are applied with other technical
lemmas to establish minimax optimal rates for the MISE. Throughout,
the universal constants become complex rather quickly and it becomes
physically impossible to track them from lines to lines. Based on
the existing mathematical tools from approximation theory, information
theory, minimax lower bounds theory, and empirical processes theory
(for upper bounds), deriving meaningful universal constants (letting
alone sharp universal constants) in the particular context of this
paper is infeasible and remains an open problem until a new mathematical
foundation can be introduced.}
The fundamental contribution of this paper lies in a set of metric
entropy bounds. Some of them are original, and some of them improve
and/or extend the ones in the literature to allow general (possibly
$k-$dependent) $R_{k}$s. Besides their applications in the empirical
processes theory and the theory of minimax lower bounds, our bounds
for the covering and packing numbers are of independent interest for
researchers working in approximation theory and discrete geometry.
\subsection{Related literature and the novelty of our results}
Here we start with a short discussion of why the phase transition
phenomenon has been overlooked in the literature while leaving the
details to the subsequent sections. For $\mathcal{U}_{\gamma+1}$
under the assumption that $R_{k}=\overline{C}\asymp1$ (which we will
refer to as the \textit{standard} $\mathcal{U}_{\gamma+1}$), Kolmogorov
and Tikhomirov (1959) show that
\begin{eqnarray}
\log(\delta-\textrm{covering number}) & \precsim & \left(\gamma+1\right)\log\frac{1}{\delta}+\delta^{\frac{-1}{\gamma+1}},\label{eq:Kolmogorov_covering}\\
\log(\delta-\textrm{packing number}) & \succsim & \delta^{\frac{-1}{\gamma+1}},\label{eq:Kolmogorov_packing}
\end{eqnarray}
for $\delta-$approximation accuracy. By (\ref{eq:sandwich}), (\ref{eq:Kolmogorov_packing})
implies
\begin{equation}
\log(\delta-\textrm{covering number})\succsim\delta^{\frac{-1}{\gamma+1}}.\label{eq:Kolmogorov_cover_lower}
\end{equation}
The minimax optimal MISE rates (as functions of $n$ and $\gamma$)
are related to choices of $\delta$ (see, e.g., Yang and Barron, 1999;
Wainwright, 2019). Virtually every paper including recent textbooks
on nonasymptotic statistics (such as Wainwright, 2019, eq. 5.17 on
p. 129) takes $\log(\delta-\textrm{covering/packing number})\asymp\delta^{\frac{-1}{\gamma+1}}$.
It would take some diligence for one to recognize that:
\begin{itemize}
\item when $\gamma+1$ and $\delta$ are large enough, taking $\log(\delta-\textrm{covering/packing number})\asymp\delta^{\frac{-1}{\gamma+1}}$
is problematic even for the \textit{standard} $\mathcal{U}_{\gamma+1}$,
because the term $\left(\gamma+1\right)\log\frac{1}{\delta}$ would
dominate $\delta^{\frac{-1}{\gamma+1}}$ in (\ref{eq:Kolmogorov_covering}),
and therefore, there is a significant gap between (\ref{eq:Kolmogorov_covering})
and (\ref{eq:Kolmogorov_cover_lower});
\item when $\gamma+1$ and $\delta$ are small enough, taking $\log(\delta-\textrm{covering/packing number})\asymp\delta^{\frac{-1}{\gamma+1}}$
is good enough for the \textit{standard} $\mathcal{U}_{\gamma+1}$,
because the term $\left(\gamma+1\right)\log\frac{1}{\delta}$ would
be dominated by $\delta^{\frac{-1}{\gamma+1}}$ in (\ref{eq:Kolmogorov_covering}),
and (\ref{eq:Kolmogorov_cover_lower}) is sharp for the \textit{standard}
$\mathcal{U}_{\gamma+1}$.
\end{itemize}
Here is a list of our discoveries:
\begin{itemize}
\item the derivation of the lower bound $\delta^{\frac{-1}{\gamma+1}}$
under $R_{k}=\overline{C}\asymp1$ in (\ref{eq:Kolmogorov_packing})
as well as the following literature for \textit{H�lder and Sobolev
classes} ignore the \textit{polynomial subclass} $\mathcal{U}_{\gamma+1,1}$;
see e.g., Wainwright (2019), Example 5.11, which inherits the lower
bound derivation in Kolmogorov and Tikhomirov (1959). The lower bound
$\delta^{\frac{-1}{\gamma+1}}$ is a lower bound for the \textit{standard
H�lder or Sobolev/ellipsoid subclass} only, and is not sharp even
for the \textit{standard} smoothness classes if $\gamma+1$ and $\delta$
are large enough;
\item the upper bound based on the arguments in Kolmogorov and Tikhomirov
(1959) for the \textit{polynomial subclass} $\mathcal{U}_{\gamma+1,1}$
is far from being tight when $R_{k}$s become large enough;
\item the upper bound based on the arguments in Mityagin (1961) and the
following literature (Wainwright, 2019, Example 5.12) for the \textit{Sobolev/ellipsoid
subclass} does not give the sharp dependence on $\gamma$ and $R_{\gamma+1}$;
\item the minimax optimal rate for MISE or its sample analogue in the existing
nonasymptotic literature is stated as $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$,
which is derived based on $\delta^{\frac{-1}{\gamma+1}}$, the metric
entropy for the \textit{standard H�lder or Sobolev subclass only}.
For example, see the last sentence in Example 13.15 of Wainwright
(2019, p.436). Also see Yang and Barron (1999, p.1591, 3rd paragraph).\footnote{For a \textit{non-standard} H�lder class, Zhu and Mirzaei (2021) apply
the argument in Kolmogorov and Tikhomirov (1959) to derive an upper
bound on the covering number. For the lower bound on the covering/packing
number, Zhu and Mirzaei (2021) simply take the classical result $\delta^{\frac{-1}{\gamma+1}}$
from Kolmogorov and Tikhomirov (1959). The consequence is, the lower
and upper error bounds have different rates, neither of which is sharp.
See Theorem \ref{thm:MISE_(k-1)!} in Appendix \ref{sec:MISE-nonstandard}
for the sharp rates.}
\end{itemize}
All these issues are addressed in this paper. Particularly, in deriving
the metric entropy bounds for the polynomial subclass $\mathcal{U}_{\gamma+1,1}$,
we develop our own arguments; in deriving the metric entropy bounds
for the ellipsoid subclass, we base our arguments on the existing
literature but use an improved truncation strategy that gives our
resulting bounds the sharp dependence on $\gamma$ and $R_{\gamma+1}$.
In contrast to those in the existing literature, our entropy bounds
enable us to reveal the phase transition phenomenon and obtain the
sharp MISE rates in the respective ``small $n$'' and ``large $n$''
regimes, associated with the standard smoothness classes as well as
non-standard smoothness classes motivated in Zhu and Mirzaei (2021).
\subsection{Organization }
The results and proofs of the paper are organized as follows.
\begin{itemize}
\item Section \ref{sec:Minimax-standard}: Minimax optimal rates in commonly
seen cases. Appendix \ref{sec:MISE-nonstandard}: Minimax optimal
rates in non-standard cases. The proofs for Section \ref{sec:Minimax-standard}
and Appendix \ref{sec:MISE-nonstandard} are given in Appendix \ref{sec:Proofs-for-MISE}.
\item Section \ref{sec:Covering-and-packing}: Covering and packing numbers.
These results are used to prove the minimax optimal MISE rates in
Section \ref{sec:Minimax-standard} and Appendix \ref{sec:MISE-nonstandard}.
The proofs for Section \ref{sec:Covering-and-packing} are given in
Appendix \ref{sec:proofs_entropy}.
\item Section \ref{sec:Discussions}: Discussions. Recommendation from the
applied literature (Section \ref{subsec:Practical-implications});
Open questions (Section \ref{subsec:Open-questions}).
\item Appendix \ref{sec:multi-dim-extensions}: Some insights about multivariate
smooth functions. The proofs for Appendix \ref{sec:multi-dim-extensions}
are given in Appendix \ref{sec:Proofs-for-multi-dim-extension}.
\item Appendix \ref{sec:Supporting-lemmas}: Additional supporting lemmas
for Appendix \ref{sec:Proofs-for-MISE}.
\end{itemize}
\section{Minimax optimal rates in commonly seen cases\label{sec:Minimax-standard}}
In this section, we revisit the minimax optimal MISE rates associated
with some commonly seen smoothness classes in the literature.
\begin{definition}[standard smoothness classes]\label{Standard smoothness classes}
Let $\overline{C}\asymp1$ be a universal constant independent of
$n$ and $\gamma$. The \textit{standard} H�lder class corresponds
to $\mathcal{U}_{\gamma+1}$ with $R_{k}=\overline{C}$ for all $k=0,...,\gamma+1$.
We define the \textit{standard} Sobolev class as follows:
\begin{align}
\mathcal{S}_{\gamma+1}:= & \{f:\,\left[0,\,1\right]\rightarrow\mathbb{R}\vert\,f\textrm{ is \ensuremath{\gamma+1} times differentiable a.e.,}\nonumber \\
& f^{(\gamma)}\textrm{ is absolutely continuous and}\left|f\right|_{\mathcal{H},\gamma+1}\leq\overline{C}\}\label{eq:sobolev_std}
\end{align}
with $\left|f\right|_{\mathcal{H},\gamma+1}$ defined in (\ref{eq:sobolev norm}).
\end{definition}
When we write $\mathcal{U}_{\gamma+1}$ or $\mathcal{S}_{\gamma+1}$
in this section, $\mathcal{U}_{\gamma+1}$ refers to the \textit{standard}
H�lder class and $\mathcal{S}_{\gamma+1}$ refers to the \textit{standard}
Sobolev class. The regression model (\ref{eq:model}) is subject to
the following conditions.
\begin{assumption}\label{Assumption 1} $\left\{ \varepsilon_{i}\right\} _{i=1}^{n}$
are independent $\mathcal{N}\left(0,\,\sigma^{2}\right)$ where $\sigma\asymp1$;
$\left\{ \varepsilon_{i}\right\} _{i=1}^{n}$ are independent of $\left\{ X_{i}\right\} _{i=1}^{n}$;
$\left\{ X_{i}\right\} _{i=1}^{n}$ are independent draws from a distribution
with density $p(x)$ on a bounded interval associated with our smoothness
classes.
\end{assumption}
The proofs for the minimax optimal rates in this section as well as
Appendix \ref{sec:MISE-nonstandard} are based on our results in Section
\ref{sec:Covering-and-packing} as well as techniques from empirical
processes, machine learning theory, and information theory, collected
in Appendix \ref{sec:Supporting-lemmas}.
\subsubsection*{Allowing for heteroscedasticity and non-Gaussian noise}
Assumption \ref{Assumption 1} is the most standard in the literature
for minimax lower bounds; see, e.g., Yang and Barron (1999), Raskutti,
et. al (2011), and Wainwright (2019). The main reason is, a minimax
lower bound derived under a more restrictive model would be a lower
bound under a less restrictive model that includes the former as a
special case. For example, a homoscedastic model is a special case
of a heteroscedastic one, and the independence of $\varepsilon_{i}$
and $X_{i}$ along with $\mathbb{E}\left(\varepsilon_{i}\right)=0$
implies $\mathbb{E}\left(\varepsilon_{i}\vert X_{i}\right)=0$. Meanwhile,
upper bounds for known estimators under less restrictive model assumptions
are typically available or can be established before developing the
minimax lower bounds. See the introduction of Chapter 15 in Wainwright
(2019) for the insights provided by minimax lower bounds.
Until very recently, Zhao and Yang (2022) find a way to allow the
noise terms to be heteroscedastic and have non-Gaussian distributions.
Specifically, Zhao and Yang (2022) consider
\begin{equation}
Y_{i}=f(X_{i})+\underset{\varepsilon_{i}}{\underbrace{\sigma(X_{i})w_{i}}},\,i=1,...,n,\label{eq:heter model}
\end{equation}
where, conditional on $X_{i}$, $Y_{i}$ has a density from a location-scale
family subjective to some rather mild conditions. This setup allows
Zhao and Yang (2022) to derive an upper bound for the Kullback-Leibler
divergence between distributions that are not Gaussian (but can be
Gaussian). The bound in Zhao and Yang (2022) can be used to relax
homoscedasticity without changing the main arguments of our proofs.
For more details related to proofs under (\ref{eq:heter model}),
we refer the interested readers to Appendix \ref{subsec:proof-allowing-for-heter-nonGaussian}
and the remark following Lemma C.1 in Appendix \ref{sec:Supporting-lemmas}
of our paper. It is worth pointing out that, when $\sigma(\cdot)$
in (\ref{eq:heter model}) ranges over the standard smoothness classes
with positive members bounded away from zero and bounded from above,
the minimax lower bounds have the same rate as those under Assumption
\ref{Assumption 1}.
As for the upper bounds (that demonstrate achievability), our proofs
are developed under a weaker assumption: conditional on $\left\{ X_{i}\right\} _{i=1}^{n}$,
$\left\{ \varepsilon_{i}\right\} _{i=1}^{n}$ are independent sub-Gaussian
random variables with zero mean and sub-Gaussian parameters at most
$\overline{\sigma}\asymp1$. This assumption is very standard in the
literature of empirical process theory (e.g., van der Vaart and Wellner,
1996; van de Geer, 2000; Zhu, 2017; Wainwright, 2019). However, to
establish minimax optimality, it is more sensible to consider a model
with the same set of assumptions on $\left\{ \varepsilon_{i}\right\} _{i=1}^{n}$
for the minimax lower bounds and upper bounds. Therefore, to focus
on the key points, we will state the results under Assumption \ref{Assumption 1}
in the main paper and Appendix \ref{sec:MISE-nonstandard} to be consistent
with the way the well-known results are presented in the literature
for minimax optimality.
\subsection{Mean integrated squared error rates\label{subsec:Mean-integrated-squared}}
\begin{theorem}[lower bounds] \textit{\label{thm:MISE-lower-standard}Suppose
Assumption \ref{Assumption 1} holds with density $p(x)$ bounded
away from zero; that is, $p(x)\geq c>0$ for some universal constant
$c$.}
\textit{(i) If
\begin{equation}
\frac{n}{\sigma^{2}}>\left(\gamma+1\right)^{2\gamma+3},\label{eq:n-lower-Theorem3.1}
\end{equation}
then we have
\begin{eqnarray*}
\inf_{\tilde{f}}\sup_{f\in\mathcal{S}_{\gamma+1}}\mathbb{E}\left(\left|\tilde{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \geq & \underline{c}_{0}\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}},\\
\inf_{\tilde{f}}\sup_{f\in\mathcal{U}_{\gamma+1}}\mathbb{E}\left(\left|\tilde{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \geq & \underline{c}_{0}\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}},
\end{eqnarray*}
for some universal constant $\underline{c}_{0}\in(0,\,1]$ independent
of $n$ and $\gamma$, and bounded away from zero. Note that $\frac{\sigma^{2}\left(\gamma+1\right)}{n}<\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$
in this case.}
\textit{(ii) If
\begin{equation}
\frac{n}{\sigma^{2}}\leq\left(\gamma+1\right)^{2\gamma+3},\label{eq:small n regime}
\end{equation}
we let $\gamma^{*}\in\left\{ 0,...,\gamma\right\} $ be the smallest
integer such that $\frac{n}{\sigma^{2}}\leq\left(\gamma^{*}+1\right)^{2\gamma^{*}+3}$.
Then we have
\begin{eqnarray*}
\inf_{\tilde{f}}\sup_{f\in\mathcal{S}_{\gamma+1}}\mathbb{E}\left(\left|\tilde{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \geq\underline{c} & \frac{\sigma^{2}\left(\gamma^{*}+1\right)}{n},\\
\inf_{\tilde{f}}\sup_{f\in\mathcal{U}_{\gamma+1}}\mathbb{E}\left(\left|\tilde{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \geq\underline{c} & \frac{\sigma^{2}\left(\gamma^{*}+1\right)}{n},
\end{eqnarray*}
for some universal constant $\underline{c}\in(0,\,1]$ independent
of $n$ and $\gamma$ such that $\underline{c}\leq\frac{\underline{c}_{0}}{2}$,
and bounded away from zero. Note that $\frac{\sigma^{2}\left(\gamma^{*}+1\right)}{n}\geq\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$
in this case.}
\end{theorem}
The proof for Theorem \ref{thm:MISE-lower-standard} is given in Section
\ref{subsec:Proof-for-MISE-lower-standard}, which relies on the constructions
behind the bound $\underline{B}_{2}$ in Lemma \ref{lm:entropy-generalized-polynomial},
Lemma \ref{lm:entropy-generalized-H=0000F6lder} and Lemma \ref{lm:entropy-ellipsoid-subclass}
in Section \ref{sec:Covering-and-packing}.
\subsubsection*{The intuition behind}
Recall from Section \ref{subsec:Classes-of-smooth} that a smoothness
class contains two subclasses: a polynomial subclass and an infinite-dimensional
nonparametric subclass such that any function $f$ in this subclass
has $f^{(k)}\left(0\right)=0$ for all $k=0,...,\gamma$. The proof
for Theorem \ref{thm:MISE-lower-standard} applies a version of the
Fano's inequality, which converts the problem into a multiple classification
problem that tries to distinguish among $M$ members in the function
classes of interest. The set of $M$ members need be sufficiently
large and is naturally connected with a packing set of the function
class.
Based on the constructions behind the bound $\underline{B}_{2}$ in
Lemma \ref{lm:entropy-generalized-polynomial}, we can show, the error
rate that prevents from distinguishing any pair of members in the
packing set of the standard $\gamma$th degree polynomial subclass
(in $\mathcal{U}_{\gamma+1}$ and $\mathcal{S}_{\gamma+1}$, respectively)
is $\frac{\sigma^{2}\left(\gamma+1\right)}{n}$. Based on Lemmas \ref{lm:entropy-generalized-H=0000F6lder}
and \ref{lm:entropy-ellipsoid-subclass}, we can show, the error rate
that prevents from distinguishing any pair of members in the packing
set of the standard $(\gamma+1)$th degree H�lder subclass and Sobolev
subclass is $\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$.
Note that
\begin{itemize}
\item when $\frac{n}{\sigma^{2}}>\left(\gamma+1\right)^{2\gamma+3}$, one
has $\frac{\sigma^{2}\left(\gamma+1\right)}{n}<\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$,
in which case the \textit{rate-minimizing} estimator (the ``min''
part of ``minimax'') would exploit the smoothness degree $\gamma$
(Theorem \ref{thm:MISE-lower-standard}(i));
\item when $\frac{n}{\sigma^{2}}\leq\left(\gamma+1\right)^{2\gamma+3}$,
one has $\frac{\sigma^{2}\left(\gamma+1\right)}{n}\geq\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$,
in which case the \textit{rate-minimizing} estimator (the ``min''
part of ``minimax'') would exploit the smoothness degree $\gamma^{*}+1$
(as detailed in Theorem \ref{thm:MISE-lower-standard}(ii)) such that
$\frac{\sigma^{2}\left(\gamma^{*}+1\right)}{n}\approx\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma^{*}+1\right)}{2\left(\gamma^{*}+1\right)+1}}$.
In particular, $\frac{\gamma^{*}+1}{n}\asymp\frac{\log n}{n\log(\log n)}$.
\end{itemize}
In deriving the minimax lower bounds, the existing nonasymptotic literature
uses the metric entropy $\delta^{\frac{-1}{\gamma+1}}$ (e.g., Wainwright,
2019, Examples 5.11 and 15.23). The entropy $\delta^{\frac{-1}{\gamma+1}}$
ignores the polynomial subclass. For more details, we refer the interested
readers to Section \ref{sec:Covering-and-packing}. Using $\delta^{\frac{-1}{\gamma+1}}$
to derive the minimax lower bound results in a rate $\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$
and overlooks the (sharper) rate in Theorem \ref{thm:MISE-lower-standard}(ii),
the ``small $n$'' regime.
The following two theorems show the achievability of the rates in
Theorem \ref{thm:MISE-lower-standard}. In particular, we show that
estimators constrained to exploit the optimal degree of smoothness
in each regime achieve the respective rate in Theorem \ref{thm:MISE-lower-standard}.
We consider the constrained nonparametric least squares estimator
(CNLS)
\begin{equation}
\hat{f}\in\arg\min_{\check{f}\in\mathcal{F}}\frac{1}{2n}\sum_{i=1}^{n}\left(y_{i}-\check{f}\left(x_{i}\right)\right)^{2}.\label{eq:least squares-1}
\end{equation}
The CNLS is commonly seen in the minimax optimality literature (e.g.,
Raskutti, et. al 2011) and the Kernel Ridge Regression (KRR) literature.
Let $k=\gamma$ in the ``large $n$'' regime and $k=\gamma^{*}$
in the ``small $n$'' regime. We consider either $\mathcal{F}=\mathcal{U}_{k+1}$
or
\begin{align*}
\mathcal{F}= & \mathcal{S}_{k+1}\\
:= & \{f:\,\left[0,\,1\right]\rightarrow\mathbb{R}\vert\,f\textrm{ is \ensuremath{k+1} times differentiable a.e.,}\\
& f^{(k)}\textrm{ is absolutely continuous and}\left|f\right|_{\mathcal{H},k+1}\leq\overline{C}\}
\end{align*}
where $\left|\cdot\right|_{\mathcal{H},k+1}$ is the norm defined
in (\ref{eq:sobolev norm}). Both cases can be of interest but the
latter is more widely implemented in practice, as we explain below.
\subsubsection*{Kernel Ridge Regression (KRR) in machine learning}
Constraining the estimators to be in $\mathcal{S}_{k+1}$ allows one
to implement (\ref{eq:least squares-1}) via kernel functions. The
following discussion is based on Wainwright (2019). Let the matrix
$\mathbb{K}_{k+1}\in\mathbb{R}^{n\times n}$ consist of entries $\frac{1}{n}\mathcal{K}_{k+1}\left(x_{i},\,x_{i^{'}}\right)$,
taking the form
\begin{eqnarray}
\mathcal{K}_{k+1}\left(x_{i},\,x_{i^{'}}\right) & = & 1+\left(x_{i}\wedge x_{i^{'}}\right)\quad\textrm{for }k=0,\label{eq:kernel_1}\\
\mathcal{K}_{k+1}\left(x_{i},\,x_{i^{'}}\right) & = & \sum_{j=0}^{k}\frac{x_{i}^{j}}{j!}\frac{x_{i^{'}}^{j}}{j!}+\int_{0}^{1}\frac{\left(x_{i}-t\right)_{+}^{k}}{k!}\frac{\left(x_{i^{'}}-t\right)_{+}^{k}}{k!}dt\quad\textrm{for }k>0,\label{eq:kernel_2}
\end{eqnarray}
where $\left(a\right)_{+}=a\vee0$. The kernel function $\mathcal{K}_{k+1,1}\left(w,\,z\right)=\sum_{j=0}^{k}\frac{w^{j}}{j!}\frac{z^{j}}{j!}$
generates the $k$th degree polynomial subspace and the kernel function
$\mathcal{K}_{k+1,2}\left(w,\,z\right)=\int_{0}^{1}\frac{\left(w-t\right)_{+}^{k}}{k!}\frac{\left(z-t\right)_{+}^{k}}{k!}dt$
for $k>0$ ($w\wedge z$ for $k=0$) generates the $(k+1)$th order
Sobolev subspace imposed with the restrictions that $f^{(j)}(0)=0$
for all $j=0,...,k$ and $f^{(k+1)}$ belongs to the space $\mathcal{L}^{2}\left[0,\,1\right]$.
When $\mathcal{F}=\mathcal{S}_{k+1}$ in (\ref{eq:least squares-1}),
$\hat{f}$ can be written as
\begin{equation}
\hat{f}\left(\cdot\right)=\frac{1}{\sqrt{n}}\sum_{i^{'}=1}^{n}\hat{\pi}_{i^{'}}\mathcal{K}_{k+1}\left(\cdot,\,x_{i^{'}}\right)\label{eq:KRR estimator}
\end{equation}
where
\begin{align}
\hat{\pi} & :=\left\{ \hat{\pi}_{i^{'}}\right\} _{i^{'}=1}^{n}=\arg\min_{\pi\in\mathbb{R}^{n}}\frac{1}{2n}\sum_{i=1}^{n}\left(y_{i}-\frac{1}{\sqrt{n}}\sum_{i^{'}=1}^{n}\pi_{i^{'}}\mathcal{K}_{k+1}\left(x_{i},\,x_{i^{'}}\right)\right)^{2}\label{eq:krr}\\
\textrm{s.t.} & \pi^{T}\mathbb{K}_{k+1}\pi\leq\overline{C}^{2}.\label{eq:constraint}
\end{align}
In particular, (\ref{eq:constraint}) comes from the representation
$\left|\check{f}\right|_{\mathcal{H},k+1}^{2}=\pi^{T}\mathbb{K}_{k+1}\pi$
when $\mathcal{F}=\mathcal{S}_{k+1}$ in (\ref{eq:least squares-1})
and $\check{f}$ takes the form $\check{f}\left(\cdot\right)=\frac{1}{\sqrt{n}}\sum_{i^{'}=1}^{n}\pi_{i^{'}}\mathcal{K}_{k+1}\left(\cdot,\,x_{i^{'}}\right)$.
The program above is convex. Hence, by the Lagrangian duality, solving
(\ref{eq:krr})--(\ref{eq:constraint}) is equivalent to solving
\begin{equation}
\hat{\pi}=\arg\min_{\pi\in\mathbb{R}^{n}}\frac{1}{2n}\sum_{i=1}^{n}\left(y_{i}-\frac{1}{\sqrt{n}}\sum_{i^{'}=1}^{n}\pi_{i^{'}}\mathcal{K}_{k+1}\left(x_{i},\,x_{i^{'}}\right)\right)^{2}+\lambda\pi^{T}\mathbb{K}_{k+1}\pi\label{eq:constraints2}
\end{equation}
for a properly chosen regularization parameter $\lambda>0$ (detailed
in the theorems concerning KRR). Consequently, the optimal weight
vector $\hat{\pi}$ takes the form
\begin{equation}
\hat{\pi}=\left(\mathbb{K}_{k+1}+\lambda I_{n}\right)^{-1}\frac{Y}{\sqrt{n}}\label{eq:optimal weight}
\end{equation}
where $Y=\left\{ Y_{i}\right\} _{i=1}^{n}$. The KRR estimators associated
with $\mathcal{S}_{k+1}$ are related to the smoothing splines methods
and Gaussian process regressions in machine learning. We refer interested
readers to Wahba (1990), Sch�lkopf and Smola (2002), as well as Rasmussen
and Williams (2006) for more details.
\begin{theorem}[upper bounds for standard Sobolev]\label{thm:MISE-upper-sobolev-std}\textit{
Suppose Assumption \ref{Assumption 1} holds. }
\textit{(i) If
\begin{equation}
\frac{n}{\sigma^{2}}>\left(\gamma+1\right)^{2\gamma+3},\label{eq:n-lower-Theorem3.2(ii)}
\end{equation}
let }$\hat{f}\left(\cdot\right)=\frac{1}{\sqrt{n}}\sum_{i^{'}=1}^{n}\hat{\pi}_{i^{'}}\mathcal{K}_{\gamma+1}\left(\cdot,\,x_{i^{'}}\right)$\textit{
where $\left\{ \hat{\pi}_{i^{'}}\right\} _{i^{'}=1}^{n}=\left(\mathbb{K}_{\gamma+1}+\lambda I_{n}\right)^{-1}\frac{Y}{\sqrt{n}}$
and $\lambda\asymp\left(\frac{1}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$.
Then we have
\begin{eqnarray*}
\sup_{f\in\mathcal{S}_{\gamma+1}}\mathbb{E}\left(\left|\hat{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \leq & \overline{c}\left[r_{1}^{2}+\exp\left\{ -cnr_{1}^{2}\right\} \right]
\end{eqnarray*}
for some positive universal constants $\overline{c}\in\left(1,\,\infty\right)$
and $c\asymp1$ (both independent of $n$ and $\gamma$ and bounded
away from zero and from above), where $r_{1}^{2}=\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$. }
\textit{(ii) If
\begin{equation}
\frac{n}{\sigma^{2}}\leq\left(\gamma+1\right)^{2\gamma+3},\label{eq:n-lower-Theorem3.2(i)}
\end{equation}
let }$\hat{f}=\frac{1}{\sqrt{n}}\sum_{i^{'}=1}^{n}\hat{\pi}_{i^{'}}\mathcal{K}_{\gamma^{*}+1}\left(\cdot,\,x_{i^{'}}\right)$\textit{
where $\left\{ \hat{\pi}_{i^{'}}\right\} _{i^{'}=1}^{n}=\left(\mathbb{K}_{\gamma^{*}+1}+\lambda I_{n}\right)^{-1}\frac{Y}{\sqrt{n}}$
with $\gamma^{*}$ defined in Theorem \ref{thm:MISE-lower-standard},
and $\lambda\asymp\frac{\gamma^{*}+1}{n}$. Then we have
\[
\sup_{f\in\mathcal{S}_{\gamma+1}}\mathbb{E}\left(\left|\hat{f}-f\right|_{2,\mathbb{P}}^{2}\right)\leq\overline{c}\left[r_{2}^{2}+\exp\left\{ -cnr_{2}^{2}\right\} \right]
\]
where $r_{2}^{2}=\frac{\sigma^{2}\left(\gamma^{*}+1\right)}{n}$. }
\end{theorem}
The proof for Theorem \ref{thm:MISE-upper-sobolev-std} is given in
Appendix \ref{subsec:Proof-for-MISE-upper-sobolev-std}.\textbf{ }
\begin{remark}
Procedures in this paper are standard formulations in modern textbooks
such as Wainwright (2019). Unresolved issues related to practical
implementations (such as the choice of the underived universal constant
in a regularization parameter) persisting in the existing literature
are not addressed in this paper.\footnote{In practical implementation, the specification of the constant in
a regularization parameter is somewhat arbitrary (without a theoretical
justification) in the existing literature. For example, Wainwright
(2019) writes ``user defined radius'' for constants similar to $\overline{C}$,
which becomes part of the universal constant in a regularization parameter.} Obviously, even with a good practical recommendation for the universal
constant in the regularization parameter $\lambda$, the orders of
$\lambda$ and the convergence rates of the upper bounds in Theorem
\ref{thm:MISE-upper-sobolev-std} stay the same. Theorem \ref{thm:MISE-upper-sobolev-std}
contributes to the existing literature in the way that, we show a
phase transition phenomenon in the upper bounds, which match the minimax
lower bounds in Theorem \ref{thm:MISE-lower-standard} in terms of
the rates (the part involving $n$ and $\gamma$ only). This phase
transition phenomenon has been overlooked in both the minimax lower
bounds and the upper bounds in the existing literature.
\end{remark}
If the smoothness degree $\gamma+1$ is known, there is a conjecture
in the literature that cross-validation will yield a regularization
parameter with the optimal order $\left(\frac{1}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$
that $\lambda$ has in Theorem \ref{thm:MISE-upper-sobolev-std} under
the classical setting where the smoothness degree $\gamma+1$ is finite
and $n\rightarrow\infty$ (e.g., van de Geer, 2000).\footnote{van de Geer (2000) states ``the optimal order'' as $\left(\frac{1}{n}\right)^{\frac{\gamma+1}{2\left(\gamma+1\right)+1}}$
as her $\lambda$ corresponds to our $\sqrt{\lambda}$.} To the best of our knowledge, this conjecture has not been proved
yet. Our results prompt a much harder question of whether cross validation
can also be used to choose a smoothness degree that \textit{adapts
to the phase transition}; that is, in the regime $\frac{n}{\sigma^{2}}\leq\left(\gamma+1\right)^{2\gamma+3}$,
choosing a smoothness degree with the order $\gamma^{*}+1$ has in
Theorem \ref{thm:MISE-upper-sobolev-std}, and in the regime $\frac{n}{\sigma^{2}}>\left(\gamma+1\right)^{2\gamma+3}$,
choosing $\gamma+1$ (also see Section \ref{subsec:Open-questions}
for a related discussion about rate adaptive estimators).
\textbf{The takeaway for applied researchers}. The conjecture and
question above are mostly of theoretical interest. Even if they are
proved eventually, using cross-validation to choose a smoothness degree
and the corresponding regularization parameter is computationally
costly. For applied researchers, the simplest takeaway from our theoretical
results is similar to the one given in the applied literature --
exploit no more than two degrees of smoothness (see Section \ref{subsec:Practical-implications}
for more discussions).
Like the Sobolev class, we can show a similar achievability result
for the H�lder class.
\begin{theorem}[upper bounds for standard H�lder]\label{thm:MISE-upper-holder-std}\textit{
Suppose Assumption \ref{Assumption 1} holds. }
\textit{(i) If
\begin{equation}
\frac{n}{\sigma^{2}}>\left(\gamma+1\right)^{2\gamma+3},\label{eq:sample size-lower-Theorem3.3}
\end{equation}
then we have
\begin{eqnarray*}
\sup_{f\in\mathcal{U}_{\gamma+1}}\mathbb{E}\left(\left|\hat{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \leq & \overline{c}\left[r_{1}^{2}+\exp\left\{ -cnr_{1}^{2}\right\} \right]
\end{eqnarray*}
for some positive universal constants $\overline{c}\in\left(1,\,\infty\right)$
and $c\asymp1$ (both independent of $n$ and $\gamma$ and bounded
away from zero and from above), where $r_{1}^{2}=\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\left(\gamma+1\right)}{2\left(\gamma+1\right)+1}}$.}
\textit{(ii) If
\begin{equation}
\frac{n}{\sigma^{2}}\leq\left(\gamma+1\right)^{2\gamma+3},\label{eq:sample size-upper-Theorem3.3}
\end{equation}
let $\hat{f}$ be (\ref{eq:least squares-1}) with $\mathcal{F}=\mathcal{U}_{\gamma^{*}+1}$
with $\gamma^{*}$ defined in Theorem \ref{thm:MISE-lower-standard}.
Then we have
\[
\sup_{f\in\mathcal{U}_{\gamma+1}}\mathbb{E}\left(\left|\hat{f}-f\right|_{2,\mathbb{P}}^{2}\right)\leq\overline{c}\left[r_{2}^{2}+\exp\left\{ -cnr_{2}^{2}\right\} \right]
\]
where $r_{2}^{2}=\frac{\sigma^{2}\left(\gamma^{*}+1\right)}{n}$. }
\end{theorem}
The proof for Theorem \ref{thm:MISE-upper-holder-std} is given in
Appendix \ref{subsec:Proof-for-MISE-upper-holder-std}.\textbf{ }
Table 1 summarizes the results in Section \ref{subsec:Mean-integrated-squared}
for easy reference.
\begin{table}[t]
{\small{}\caption{Minimax optimal MISE bounds of the commonly seen $\left(\gamma+1\right)$th
degree Sobolev and H�lder classes}
\medskip{}
}{\small\par}
\centering{}
\begin{tabular}{c|c|c}
\hline
& {\scriptsize{}$\frac{n}{\sigma^{2}}\leq\left(\gamma+1\right)^{2\gamma+3}$} & {\scriptsize{}$\frac{n}{\sigma^{2}}>\left(\gamma+1\right)^{2\gamma+3}$}\tabularnewline
\hline
{\scriptsize{}MISE} & {\scriptsize{}$\in\left[\underline{c}\frac{\sigma^{2}\left(\gamma^{*}+1\right)}{n},\:c^{'}\frac{\sigma^{2}\left(\gamma^{*}+1\right)}{n}\right]$} & {\scriptsize{}$\in\left[\underline{c}_{0}\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}},\,c^{'}\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}\right]$}\tabularnewline
\hline
\end{tabular}\\
{\scriptsize{}where: $\underline{c},\,\underline{c}_{0},\,c^{'}\asymp1$
are positive universal constants that are independent of $n$ and
$\gamma$, and $\underline{c}\leq\frac{\underline{c}_{0}}{2}$; $\gamma^{*}$
is the smallest integer in $\left\{ 0,...,\gamma\right\} $ such that
$\frac{n}{\sigma^{2}}\leq\left(\gamma^{*}+1\right)^{2\gamma^{*}+3}$.}{\scriptsize\par}
\end{table}
\subsection{The sample mean squared error rates}
When deriving the upper bounds in Theorems \ref{thm:MISE-upper-sobolev-std}
and \ref{thm:MISE-upper-holder-std}, we obtain the following bounds
on the sample mean squared error (SMSE) as intermediate results.
\begin{corollary} \textit{Suppose the conditions in Theorem }\ref{thm:MISE-upper-sobolev-std}\textit{
hold. Under (\ref{eq:n-lower-Theorem3.2(ii)}), we have
\[
\left|\hat{f}-f\right|_{n}^{2}\precsim r_{1}^{2}\quad\textrm{for any }f\in\mathcal{S}_{\gamma+1},
\]
with probability at least $1-c_{0}\exp\left\{ -cnr_{1}^{2}\right\} $.
Under (\ref{eq:n-lower-Theorem3.2(i)}), we have
\[
\left|\hat{f}-f\right|_{n}^{2}\precsim r_{2}^{2}\quad\textrm{for any }f\in\mathcal{S}_{\gamma+1},
\]
with probability at least $1-c_{0}\exp\left\{ -cnr_{2}^{2}\right\} $. }
\end{corollary}
\begin{corollary}\textit{ Suppose the conditions in Theorem \ref{thm:MISE-upper-holder-std}
hold. Under (\ref{eq:sample size-lower-Theorem3.3}), we have
\[
\left|\hat{f}-f\right|_{n}^{2}\precsim r_{1}^{2}\quad\textrm{for any }f\in\mathcal{U}_{\gamma+1},
\]
with probability at least $1-c_{0}\exp\left\{ -cnr_{1}^{2}\right\} $.
Under (\ref{eq:sample size-upper-Theorem3.3}), we have
\[
\left|\hat{f}-f\right|_{n}^{2}\precsim r_{2}^{2}\quad\textrm{for any }f\in\mathcal{U}_{\gamma+1},
\]
with probability at least $1-c_{0}\exp\left\{ -cnr_{2}^{2}\right\} $. }
\end{corollary}
\subsection{Infinitely smooth functions \label{subsec:Analytic-functions-as}}
In this subsection, we consider infinitely differentiable functions
with the following form
\begin{equation}
f(x)=f(0)+\sum_{k=1}^{\infty}\frac{x^{k}}{k!}f^{(k)}(0).\label{eq:expansion-1}
\end{equation}
The standard $\mathcal{U}_{\infty}$ for infinitely smooth functions
follows the definition of the standard $\mathcal{U}_{\gamma+1}$ with
$\gamma+1=\infty$. The analog of $\mathcal{S}_{\gamma+1}$ in (\ref{eq:sobolev_std})
for infinitely smooth functions can be defined as
\begin{align*}
\mathcal{S}_{\infty} & :=\{f:\,\left[0,\,1\right]\rightarrow\mathbb{R}\vert\,f\textrm{ is infinitely differentiable,}\\
& \sum_{j=0}^{\infty}\left(f^{(j)}(0)\right)^{2}\leq\overline{C}^{2}\}
\end{align*}
where $\overline{C}\asymp1$ is a universal constant independent of
$n$ and $\gamma$.
We have the following result for analytic functions.
\begin{corollary}[analytic functions] \label{corr:analytic functions}\textit{Suppose
Assumption \ref{Assumption 1} holds. For the minimax lower bounds,
we further assume that the density $p(x)$ is bounded away from zero;
that is, $p(x)\geq c>0$ for some universal constant $c$. Given a
sample size $n$, let $\gamma^{*}\in\left\{ 0,...,\gamma\right\} $
be the smallest integer such that $\frac{n}{\sigma^{2}}\leq\left(\gamma^{*}+1\right)^{2\gamma^{*}+3}$.
Then we have
\begin{eqnarray*}
\inf_{\tilde{f}}\sup_{f\in\mathcal{S}_{\infty}}\mathbb{E}\left(\left|\tilde{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \geq & \underline{c}r_{2}^{2},\\
\sup_{f\in\mathcal{S}_{\infty}}\mathbb{E}\left(\left|\hat{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \leq & \overline{c}\left[r_{2}^{2}+\exp\left\{ -cnr_{2}^{2}\right\} \right],
\end{eqnarray*}
for some positive universal constants $\underline{c},\,\overline{c},\,c\asymp1$
that are independent of $n$ and $\gamma$, where $\hat{f}$ and }$r_{2}$\textit{
are defined in Theorem \ref{thm:MISE-upper-sobolev-std}(ii).}
\textit{Let $\hat{f}$ be (\ref{eq:least squares-1}) with $\mathcal{F}=\mathcal{U}_{\gamma^{*}+1}$.
Then we also have }
\textit{
\begin{eqnarray*}
\inf_{\tilde{f}}\sup_{f\in\mathcal{U}_{\infty}}\mathbb{E}\left(\left|\tilde{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \geq & \underline{c}r_{2}^{2},\\
\sup_{f\in\mathcal{U}_{\infty}}\mathbb{E}\left(\left|\hat{f}-f\right|_{2,\mathbb{P}}^{2}\right) & \leq & \overline{c}\left[r_{2}^{2}+\exp\left\{ -cnr_{2}^{2}\right\} \right],
\end{eqnarray*}
for some positive universal constants $\underline{c},\,\overline{c},\,c\asymp1$
that are independent of $n$ and $\gamma$.}
\end{corollary}
The proof for the lower bound in Corollary \ref{corr:analytic functions}
is identical to the proof for part (ii) of Theorem \ref{thm:MISE-lower-standard}
(Appendix \ref{subsec:Proof-for-MISE-lower-standard}). The proofs
for the upper bounds in Corollary \ref{corr:analytic functions} involve
only slight modifications of Appendix \ref{subsec:Proof-for-MISE-upper-sobolev-std}
and Appendix \ref{subsec:Proof-for-MISE-upper-holder-std}. See Appendix
\ref{subsec:Proof-for-analytic_MISE}.
There is no phase transition in the optimal rate associated with $\mathcal{U}_{\infty}$
and $\mathcal{S}_{\infty}$. As discussed earlier, $\frac{\gamma^{*}+1}{n}\asymp\frac{\log n}{n\log(\log n)}$.
Relatedly, see a review article about the estimation of analytic functions
by Ibragimov (2001), in particular, Theorem 4.9 where the minimax
optimal rate for the MISE associated with analytic functions is $\frac{\log n}{n\log(\log n)}$.\footnote{The author thanks an anonymous referee for pointing out this reference.}
Corollary \ref{corr:analytic functions} highlights the importance
of our results on phase transition in this paper. Stating $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
as the minimax optimal rate for MISE associated with a standard smoothness
class without a condition on $n$ raises the following ``paradox''.
Recall (\ref{eq:asymptotic interpretation}); on the other hand, $\mathcal{U}_{\infty}\subseteq\mathcal{U}_{\gamma+1}$
so (\ref{eq:asymptotic interpretation}) is not plausible if $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
is stated \textit{alone}, without a condition on $n$, as the minimax
optimal rate in MISE for the standard $\mathcal{U}_{\gamma+1}$. Our
results in Section \ref{subsec:Mean-integrated-squared} are crucial
for reconciling the aforementioned ``paradox'', as the choice of
our critical smoothness parameter $\gamma^{*}+1$ guarantees that:
\begin{itemize}
\item in the ``small $n$'' regime, the minimax optimal rate associated
with $\mathcal{U}_{\gamma+1}$ is $\frac{\gamma^{*}+1}{n}\asymp\frac{\log n}{n\log(\log n)}$;
\item in the ``large $n$'' regime, the minimax optimal rate associated
with $\mathcal{U}_{\gamma+1}$ is $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
and
\[
\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}\succsim\frac{\gamma+1}{n}\geq\frac{\gamma^{*}+1}{n}\asymp\frac{\log n}{n\log(\log n)}.
\]
\end{itemize}
Assuming $\sigma\asymp1$, a better practice would be to state the
rate $\left(\frac{\sigma^{2}}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
under the condition $\frac{n}{\sigma^{2}}>\left(\gamma+1\right)^{2\gamma+3}$
and the rate $\frac{\sigma^{2}\log n}{n\log(\log n)}$ under the condition
$\frac{n}{\sigma^{2}}\leq\left(\gamma+1\right)^{2\gamma+3}$, as shown
in this paper.
\section{Covering and packing numbers \label{sec:Covering-and-packing}}
In this section, we present bounds on covering and packing numbers
associated with $\mathcal{U}_{\gamma+1,1}$, $\mathcal{U}_{\gamma+1,2}$,
and $\mathcal{H}_{\gamma+1}$. Various $c$ and $C$ letters in this
section denote positive universal constants that are: finite and bounded
away from zero (denoted by $\asymp1$) and independent of $\gamma$
and $\left\{ R_{k}\right\} _{k=0}^{\gamma+1}$ (parameters of the
function classes); these constants may vary from place to place.
Table 2 summarizes the results in this section for easy reference.
\begin{table}
{\footnotesize{}\caption{Upper and lower bounds on the $\log(\delta-\textrm{covering number})$
and $\log(\delta-\textrm{packing number})$ of the generalized $\mathcal{U}_{\gamma+1,1}$,
$\mathcal{U}_{\gamma+1,2}$ and $\mathcal{H}_{\gamma+1}$ in $L^{q}-$norm}
}{\small{}\medskip{}
}{\small\par}
\begin{centering}
{\scriptsize{}}
\begin{tabular}{c|c||c||c||c||c}
\hline
\multicolumn{1}{c}{} & \multicolumn{2}{c||}{{\scriptsize{}$\mathcal{U}_{\gamma+1,1}$ ($q\in\left\{ 2,\,\infty\right\} $)}} & \multicolumn{2}{c||}{{\scriptsize{}$\mathcal{U}_{\gamma+1,2}$ ($q\in\left\{ 2,\,\infty\right\} $)}} & {\scriptsize{}$\mathcal{H}_{\gamma+1}$ ($q=2$)}\tabularnewline
\hline
{\scriptsize{}$\precsim$} & \multicolumn{2}{c||}{{\scriptsize{}$\begin{cases}
\overline{B}_{1}\left(\delta\right) & \textrm{if }\min_{k\in\left\{ 0,...,\gamma\right\} }\log\frac{4\left(\gamma+1\right)R_{k}}{k!\delta}\geq0\\
\overline{B}_{2}\left(\delta\right) & \textrm{otherwise}
\end{cases}$}} & \multicolumn{2}{c||}{{\scriptsize{}$R^{*\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}}$}} & {\scriptsize{}$\begin{cases}
R_{\gamma+1}^{\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}} & \textrm{if }R_{\gamma+1}\succsim\gamma+1\\
\delta^{\frac{-1}{\gamma+1}} & \textrm{if }R_{\gamma+1}\precsim\gamma+1
\end{cases}$}\tabularnewline
\hline
{\scriptsize{}$\succsim$} & \multicolumn{2}{c||}{{\scriptsize{}$\max\left\{ \underline{B}_{1}\left(\delta\right),\,\underline{B}_{2}\right\} $}} & \multicolumn{2}{c||}{{\scriptsize{}$\begin{cases}
R^{*\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}} & \textrm{if }R_{0}\succsim1\\
\left(R^{*}R_{0}\right)^{\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}} & \textrm{if }R_{0}\precsim1
\end{cases}$}} & {\scriptsize{}$R_{\gamma+1}^{\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}}$}\tabularnewline
\hline
\end{tabular}{\scriptsize\par}
\par\end{centering}
\centering{}{\scriptsize{}where: $\overline{B}_{1}\left(\delta\right)=\sum_{k=0}^{\gamma}\log\frac{4\left(\gamma+1\right)R_{k}}{k!\delta}$;
$\overline{B}_{2}\left(\delta\right)=\left(\frac{\gamma}{2}+1\right)\log\frac{1}{\delta}+\sum_{k=0}^{\gamma}\log R_{k}$;
$\underline{B}_{1}\left(\delta\right)=\sum_{k=0}^{\gamma}\log\left(9^{-\gamma}\gamma^{-\gamma}\right)+\sum_{k=0}^{\gamma}\log\frac{C\sum_{m=0}^{\left\lfloor \gamma/2\right\rfloor }R_{k+2m}}{\delta}$
(with $R_{k+2m}=0$ for $k+2m>\gamma$); $\underline{B}_{2}=C^{'}\left(\gamma+1\right)$
(valid for all $\delta$ below a threshold detailed in Lemma 3.1);
$R^{*}=\left(\max_{k\in\left\{ 1,...,\gamma+1\right\} }\frac{R_{k}}{\left(k-1\right)!}\right)\vee1$;
$C$ and $C^{'}$ are positive universal constants that are: $\asymp1$,
independent of $\gamma$ and $\left\{ R_{k}\right\} _{k=0}^{\gamma+1}$.}{\scriptsize\par}
\end{table}
\subsection{The generalized polynomial subclass, $\mathcal{U}_{\gamma+1,1}$}
\begin{lemma}\label{lm:entropy-generalized-polynomial} \textit{(i)
If $\delta$ is small enough such that $\min_{k\in\left\{ 0,...,\gamma\right\} }\log\frac{4\left(\gamma+1\right)R_{k}}{k!\delta}\geq0$,
we have
\begin{align}
\log N_{2,\mathbb{P}}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right) & \leq\log N_{\infty}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right)\leq\underset{\overline{B}_{1}\left(\delta\right)}{\underbrace{\sum_{k=0}^{\gamma}\log\frac{4\left(\gamma+1\right)R_{k}}{k!\delta}}};\label{eq:b1_upper_Lemma3.1}
\end{align}
if $\delta$ is large enough such that $\min_{k\in\left\{ 0,...,\gamma\right\} }\log\frac{4\left(\gamma+1\right)R_{k}}{k!\delta}<0$,
we have
\begin{equation}
\log N_{2,\mathbb{P}}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right)\leq\log N_{\infty}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right)\leq\underset{\overline{B}_{2}\left(\delta\right)}{\underbrace{\left(\frac{\gamma}{2}+1\right)\log\frac{1}{\delta}+\sum_{k=0}^{\gamma}\log R_{k}}}.\label{eq:Kolmogorov_upper-1-1}
\end{equation}
}
\textit{(ii) In terms of the lower bounds, we have
\begin{eqnarray*}
\log M_{2}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right) & \geq & \underline{B}_{1}\left(\delta\right),\\
\log M_{\infty}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right) & \succsim & \underline{B}_{1}\left(\delta\right),
\end{eqnarray*}
where $\underline{B}_{1}\left(\delta\right)=\sum_{k=0}^{\gamma}\log\left(9^{-\gamma}\gamma^{-\gamma}\right)+\sum_{k=0}^{\gamma}\log\frac{C\sum_{m=0}^{\left\lfloor \gamma/2\right\rfloor }R_{k+2m}}{\delta}$
(with $R_{k+2m}=0$ for $k+2m>\gamma$) for some positive universal
constant $C\asymp1$ independent of $\gamma$ and $\left\{ R_{k}\right\} _{k=0}^{\gamma}$.
Let $\tilde{k}\in\arg\max_{k\in\left\{ 0,...,\gamma\right\} }\frac{R_{k}}{k!}$.
If
\begin{equation}
\frac{R_{\tilde{k}}}{\tilde{k}!\delta\left[\left(\tilde{k}+1\right)\vee\sum_{k=0}^{\gamma}\frac{R_{k}}{k!}\right]}\succsim2^{\gamma+1},\label{eq:6}
\end{equation}
we also have
\begin{eqnarray}
\log M_{2}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right) & \geq & \underline{B}_{2}=C^{'}\left(\gamma+1\right),\label{eq:10}\\
\log M_{\infty}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right) & \succsim & \underline{B}_{2},\nonumber
\end{eqnarray}
for some positive universal constant $C^{'}\asymp1$ independent of
$\gamma$ and $\left\{ R_{k}\right\} _{k=0}^{\gamma}$.}
\textit{(iii) If the density function $p(x)$ on $\left[-1,\,1\right]$
is bounded away from zero, i.e., $p(x)\geq c>0$, then
\begin{equation}
\log M_{2,\mathbb{P}}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right)\succsim\underline{B}_{1}\left(\delta\right);\label{eq:b1_lower_Lemma3.1}
\end{equation}
under (\ref{eq:6}), we also have
\begin{equation}
\log M_{2,\mathbb{P}}\left(\delta,\,\mathcal{U}_{\gamma+1,1}\right)\succsim\underline{B}_{2}.\label{eq:b2_lower_Lemma3.1}
\end{equation}
}
\end{lemma}
\begin{remark} When $R_{k}=\overline{C}$ for $k=0,...,\gamma$,
$\left(\tilde{k}+1\right)\vee\sum_{k=0}^{\gamma}\frac{R_{k}}{k!}\asymp1$;
when $R_{0}=\overline{C}$ and $R_{k}\leq\overline{C}\left(k-1\right)!$
for $k=1,...,\gamma$, $\left(\tilde{k}+1\right)\vee\sum_{k=0}^{\gamma}\frac{R_{k}}{k!}\precsim\log\left(\gamma\vee2\right)$;
when $R_{k}=\overline{C}k!$ for all $k=0,...,\gamma$, $\left(\tilde{k}+1\right)\vee\sum_{k=0}^{\gamma}\frac{R_{k}}{k!}\asymp\left(\gamma\vee1\right)$.
\end{remark}
The proof for Lemma \ref{lm:entropy-generalized-polynomial} is given
in Appendix \ref{subsec:Proof-for-entropy-poly}.
The lower bounds $\underline{B}_{1}\left(\delta\right)$ and $\underline{B}_{2}$,
as well as the upper bound $\overline{B}_{1}\left(\delta\right)$
are original. The (less original) bound $\overline{B}_{2}\left(\delta\right)$
generalizes the upper bound associated with the polynomial subclass
in Kolmogorov and Tikhomirov (1959), which takes the form $\left(\gamma+1\right)\log\frac{1}{\delta}$.
It is worth pointing out that $\overline{B}_{2}\left(\delta\right)$
holds for all $\delta\in(0,\,1)$ (not just $\delta$ such that \textit{$\min_{k\in\left\{ 0,...,\gamma\right\} }\log\frac{4\left(\gamma+1\right)R_{k}}{k!\delta}<0$})
but is far from being tight when $\min_{k\in\left\{ 0,...,\gamma\right\} }\log\frac{4\left(\gamma+1\right)R_{k}}{k!\delta}\geq0$.
Obviously $\overline{B}_{1}\left(\delta\right)\precsim\overline{B}_{2}\left(\delta\right)$.
When it comes to deriving the minimax optimal rates for the MISE under
large enough $R_{k}$ (e.g., Theorems \ref{thm:MISE_(k-1)!} and \ref{thm:MISE_k!}
in Appendix \ref{sec:MISE-nonstandard}), $\overline{B}_{1}\left(\delta\right)$
will be very useful.
When deriving a lower bound for the packing number of the \textit{standard}
$\mathcal{U}_{\gamma+1}$ under the assumption that $R_{k}=\overline{C}\asymp1$,
Kolmogorov and Tikhomirov (1959) constructs a set of functions where
$\mathcal{U}_{\gamma+1,1}$ is a singleton; therefore, the cardinality
of this set only gives a lower bound for the packing number of $\mathcal{U}_{\gamma+1,2}$
and overlooks $\mathcal{U}_{\gamma+1,1}$. This issue is further discussed
in Section \ref{subsec:entropy-generalized-H=0000F6lder}. Our Lemma
\ref{lm:entropy-generalized-polynomial} establishes two different
lower bounds for the packing number of $\mathcal{U}_{\gamma+1,1}$.
In particular, the construction of $\underline{B}_{2}$ in (\ref{eq:b2_lower_Lemma3.1})
will be useful for deriving the minimax lower bounds for the MISE
when $R_{k}$ is relatively small (e.g., Theorem \ref{thm:MISE-lower-standard}
in Section \ref{sec:Minimax-standard} and Theorem \ref{thm:MISE_(k-1)!}
in Appendix \ref{sec:MISE-nonstandard}), while $\underline{B}_{1}\left(\delta\right)$
in (\ref{eq:b1_upper_Lemma3.1}) will be useful when $R_{k}$ is relatively
large (Theorem \ref{thm:MISE_k!} in Appendix \ref{sec:MISE-nonstandard}).
To establish $\overline{B}_{1}\left(\delta\right)$, $\underline{B}_{1}\left(\delta\right)$
and $\underline{B}_{2}$, we discard the argument in Kolmogorov and
Tikhomirov (1959) and develop our own. The derivation of $\underline{B}_{2}$
is based on a constructive proof. To derive $\overline{B}_{1}\left(\delta\right)$
and $\underline{B}_{1}\left(\delta\right)$, we consider two classes
(equivalent to $\mathcal{U}_{\gamma+1,1}$), each involving a $\left(\gamma+1\right)-$dimensional
polyhedron. The lower bound $\underline{B}_{1}\left(\delta\right)$
is the more delicate part. In particular, for any $f\in\mathcal{U}_{\gamma+1,1}$,
we write $f\left(x\right)=\sum_{k=0}^{\gamma}\tilde{\theta}_{k}\phi_{k}\left(x\right)$,
where $\left(\phi_{k}\right)_{k=0}^{\gamma}$ are the Legendre polynomials.
\subsection{The generalized H�lder subclass, $\mathcal{U}_{\gamma+1,2}$\label{subsec:entropy-generalized-H=0000F6lder}}
\begin{lemma} \textit{\label{lm:entropy-generalized-H=0000F6lder}Let
$R^{*}=\left(\max_{k\in\left\{ 1,...,\gamma+1\right\} }\frac{R_{k}}{\left(k-1\right)!}\right)\vee1$.
We have
\begin{align*}
\log N_{2,\mathbb{P}}\left(\delta,\,\mathcal{U}_{\gamma+1,2}\right) & \leq\log N_{\infty}\left(\delta,\,\mathcal{U}_{\gamma+1,2}\right)\precsim R^{*\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}}.
\end{align*}
We also have
\begin{eqnarray*}
\log M_{\infty}\left(\delta,\,\mathcal{U}_{\gamma+1,2}\right) & \succsim & \log M_{2}\left(\delta,\,\mathcal{U}_{\gamma+1,2}\right)\succsim R^{*\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}},\quad\textrm{if }R_{0}\succsim1,\,\delta\in(0,\,1);\\
\log M_{\infty}\left(\delta,\,\mathcal{U}_{\gamma+1,2}\right) & \succsim & \log M_{2}\left(\delta,\,\mathcal{U}_{\gamma+1,2}\right)\succsim\left(R^{*}R_{0}\right)^{\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}},\quad\textrm{if }R_{0}\precsim1,\,\delta\in(0,\,1).
\end{eqnarray*}
If the density function $p(x)$ on $\left[-1,\,1\right]$ is bounded
away from zero, i.e., $p(x)\geq c>0$, then
\begin{eqnarray*}
\log M_{2,\mathbb{P}}\left(\delta,\,\mathcal{U}_{\gamma+1,2}\right) & \succsim & R^{*\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}},\quad\textrm{if }R_{0}\succsim1,\,\delta\in(0,\,1);\\
\log M_{2,\mathbb{P}}\left(\delta,\,\mathcal{U}_{\gamma+1,2}\right) & \succsim & \left(R^{*}R_{0}\right)^{\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}},\quad\textrm{if }R_{0}\precsim1,\,\delta\in(0,\,1).
\end{eqnarray*}
}
\end{lemma}
The proof for Lemma \ref{lm:entropy-generalized-H=0000F6lder} is
given in Appendix \ref{subsec:Proof-for-entropy-holder-sub}. Lemma
\ref{lm:entropy-generalized-polynomial} and Lemma \ref{lm:entropy-generalized-H=0000F6lder}
together are used to prove Theorems \ref{thm:MISE-lower-standard}
and \ref{thm:MISE-upper-holder-std} in Section \ref{sec:Minimax-standard},
as well as Theorems \ref{thm:MISE_(k-1)!} and \ref{thm:MISE_k!}
in Appendix \ref{sec:MISE-nonstandard}; in addition, Lemma \ref{lm:entropy-generalized-H=0000F6lder}
is also used to prove Theorem \ref{thm:MISE-gen-sub-ellipsoid}(ii)
in Appendix \ref{sec:MISE-nonstandard}.
Lemma \ref{lm:entropy-generalized-H=0000F6lder} extends Kolmogorov
and Tikhomirov (1959) to allow for general $R_{k}$s. When $R_{k}\leq\overline{C}k!$
for all $k=1,...,\gamma+1$, $R^{*\frac{1}{\gamma+1}}\asymp1$. If
$R_{k}\geq\overline{C}k!$ for all $k=1,...,\gamma+1$, $R^{*\frac{1}{\gamma+1}}\succsim1$;
for example, taking $R_{k}\geq\overline{C}\left(k!\right)^{2}$ for
all $k=1,...,\gamma+1$ yields $R^{*\frac{1}{\gamma+1}}\succsim\gamma$.
Given Lemmas \ref{lm:entropy-generalized-polynomial} and \ref{lm:entropy-generalized-H=0000F6lder},
(\ref{eq:inner}) and (\ref{eq:outter}), we have
\begin{align}
\log N_{2,\mathbb{P}}\left(2\delta,\,\mathcal{U}_{\gamma+1}\right) & \leq\log N_{\infty}\left(2\delta,\,\mathcal{U}_{\gamma+1}\right)\nonumber \\
& \leq\begin{cases}
\overline{B}_{1}\left(\delta\right)+R^{*\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}} & \textrm{if }\min_{k\in\left\{ 0,...,\gamma\right\} }\log\frac{4\left(\gamma+1\right)R_{k}}{k!\delta}\geq0\\
\overline{B}_{2}\left(\delta\right)+R^{*\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}} & \textrm{if }\min_{k\in\left\{ 0,...,\gamma\right\} }\log\frac{4\left(\gamma+1\right)R_{k}}{k!\delta}<0
\end{cases}\label{eq:upper_together}
\end{align}
and
\[
\log M_{\infty}\left(\delta,\,\mathcal{U}_{\gamma+1}\right)\succsim\log M_{2}\left(\delta,\,\mathcal{U}_{\gamma+1}\right)\succsim\begin{cases}
\max\left\{ \underline{B}_{1}\left(\delta\right),\,\underline{B}_{2},\,R^{*\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}}\right\} & \textrm{if }R_{0}\succsim1\\
\max\left\{ \underline{B}_{1}\left(\delta\right),\,\underline{B}_{2},\,\left(R^{*}R_{0}\right)^{\frac{1}{\gamma+1}}\delta^{\frac{-1}{\gamma+1}}\right\} & \textrm{if }R_{0}\precsim1
\end{cases}.
\]
Our lower bounds above sharpen the classical result in Kolmogorov
and Tikhomirov (1959). In particular, the lower bound for $\mathcal{U}_{\gamma+1}$
in Kolmogorov and Tikhomirov (1959) (derived under the assumption
that $R_{k}=\overline{C}\asymp1$) takes the form $\delta^{\frac{-1}{\gamma+1}}$.
This result and its proof are inherited later in papers and textbooks
including the more recent textbook on nonasymptotic statistics by
Wainwright (2019, Example 5.11), where in the derivation of the lower
bound, a set of functions are constructed in the way such that their
$k$th order derivatives evaluated at zero are zero for all $k=0,...,\gamma$.
In other words, $\mathcal{U}_{\gamma+1,1}$ is a singleton in this
construction and the cardinality of this set only gives a lower bound
for $\mathcal{U}_{\gamma+1,2}$. In particular, the lower bound $\delta^{\frac{-1}{\gamma+1}}$
is not sharp when $\gamma+1$ and $\delta$ are large enough.
\subsection{The ellipsoid subclass, $\mathcal{H}_{\gamma+1}$}
\begin{lemma}\label{lm:entropy-ellipsoid-subclass} \textit{Assume
$\mu_{m}=\left(cm\right)^{-2\left(\gamma+1\right)}$ in (\ref{eq:Ellipsoid-1})
for a positive constant $c\asymp1$ independent of $\gamma$ and $R_{\gamma+1}$.
If $R_{\gamma+1}\succsim\gamma+1$, we have
\[
\log N_{2}\left(\delta,\,\mathcal{H}_{\gamma+1}\right)\asymp\left(R_{\gamma+1}\delta^{-1}\right)^{\frac{1}{\gamma+1}}.
\]
If $R_{\gamma+1}\precsim\gamma+1$, we have
\begin{align}
\log N_{2}\left(\delta,\,\mathcal{H}_{\gamma+1}\right) & \precsim\delta^{\frac{-1}{\gamma+1}},\label{eq:15-1}\\
\log N_{2}\left(\delta,\,\mathcal{H}_{\gamma+1}\right) & \succsim\left(R_{\gamma+1}\delta^{-1}\right)^{\frac{1}{\gamma+1}}.\label{eq:15}
\end{align}
If the density function $p(x)$ on $\left[0,\,1\right]$ is bounded
away from zero, i.e., $p(x)\geq c>0$, then the bounds above also
hold for $\log N_{2,\mathbb{P}}\left(\delta,\,\mathcal{H}_{\gamma+1}\right)$.}
\end{lemma}
The proof for Lemma \ref{lm:entropy-ellipsoid-subclass} is given
in Appendix \ref{subsec:Proof-for-entropy_ellipsoid_sub}. Lemma \ref{lm:entropy-generalized-polynomial}
and Lemma \ref{lm:entropy-ellipsoid-subclass} together are used to
prove Theorem \ref{thm:MISE-lower-standard}. Lemma \ref{lm:entropy-ellipsoid-subclass}
is also used to prove Theorem \ref{thm:MISE-gen-sub-ellipsoid}(i)
in Appendix \ref{sec:MISE-nonstandard}.
When $R_{\gamma+1}=1$, Lemma \ref{lm:entropy-ellipsoid-subclass}
sharpens the upper bound for $\log N_{2}\left(\delta,\,\mathcal{H}_{\gamma+1}\right)$
in Wainwright (2019) from $\left(\gamma\vee1\right)\delta^{-\frac{1}{\gamma+1}}$
to $\delta^{-\frac{1}{\gamma+1}}$; in particular, the upper and lower
bounds in Wainwright (2019) (the last two inequalities on p.131) scale
as $\left(\gamma\vee1\right)\delta^{\frac{-1}{\gamma+1}}$ and $\delta^{\frac{-1}{\gamma+1}}$,
respectively, while our upper and lower bounds in Lemma \ref{lm:entropy-ellipsoid-subclass}
have the same scaling $\delta^{\frac{-1}{\gamma+1}}$. We discover
the cause of the gap lies in that the ``pivotal'' eigenvalue (that
balances the ``estimation error'' and the ``approximation error''
from truncating for a given resolution $\delta$) in Wainwright (2019)
is not optimal. The truncation in Wainwright (2019) is commonly used
in the existing literature and seems to originate from Theorem 3 in
Mityagin (1961). We close the gap by finding the optimal ``pivotal''
eigenvalue.
More generally, for the case of $R_{\gamma+1}\precsim\gamma+1$, we
consider two different truncations, one giving the upper bound $\delta^{\frac{-1}{\gamma+1}}$
and the other giving the lower bound $\left(R_{\gamma+1}\delta^{-1}\right)^{\frac{1}{\gamma+1}}$.
Note that $\left(R_{\gamma+1}\delta^{-1}\right)^{\frac{1}{\gamma+1}}\asymp\delta^{\frac{-1}{\gamma+1}}$
when $R_{\gamma+1}\asymp1$. For the case of $R_{\gamma+1}\succsim\gamma+1$,
we use only one truncation to show that both the upper bound and the
lower bound scale as $\left(R_{\gamma+1}\delta^{-1}\right)^{\frac{1}{\gamma+1}}$.
\section{Discussions\label{sec:Discussions}}
\subsection{Recommendation from the applied literature \label{subsec:Practical-implications}}
In the discussion following Theorem \ref{thm:MISE-lower-standard},
we have brought up the trade-off between the polynomial subclass and
the nonparametric subclass. It is worth mentioning the connection
between our theoretical results and the empirical findings from Gelman
and Imbens (2019), which implements high order polynomials in regression
discontinuity designs (RDD) analyses. In particular, when applying
RDD to perform causal inference, two conditional mean functions of
a pretreatment variable are estimated from (\ref{eq:model}). There
are several empirical issues of using high order polynomials raised
in Gelman and Imbens (2019). The implication of our results is most
related to their paper on the issue of mean squared errors (MSE).
Regarding the data sets studied in Gelman and Imbens (2019), the Jacob-Lefgren
data (Jacob and Lefgren, 2004), Lee data (Lee, 2008), Matsudaira data
(Matsudaira, 2008), the LaLonde data (LaLonde, 1986), and the census
data in 1974, 1975 and 1978, the sample sizes used in the implementation
of Gelman and Imbens (2019) range from thousands to at most thirties
of thousands. Based on their empirical evidence from studying these
data sets, Gelman and Imbens (2019) recommend researchers to avoid
using high order polynomials but use local linear or local quadratic
polynomials. In view of the asymptotic condition $\left(\gamma+1\right)^{2\gamma+3}=o(n)$
for the rate $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
to kick in (see (\ref{eq:asymptotic condition_1})), let us solve
for $\overline{\gamma}+1$ roughly from $n\geq\left(\overline{\gamma}+1\right)^{2\overline{\gamma}+3}$.
This \textit{heuristic} gives a rough degree of smoothness to exploit,
$\max\left\{ \left\lfloor \frac{\log n}{2\log\left(\log n\right)}\right\rfloor ,\,1\right\} $,
which is quite close to the recommended smoothness degrees in Gelman
and Imbens (2019).
\subsection{Open questions\label{subsec:Open-questions}}
We conclude the paper by discussing a few open questions motivated
by this work. First, our focus in this paper is on the global criterion
MISE while the concern of Gelman and Imbens (2019) is about the MSE
of the high order polynomial implementation at a point. The minimax
optimality of pointwise MSE and the global MISE (concerning an entire
function) would involve different proofs. It is well known that the
minimax optimal MISE rate coincides with the minimax optimal pointwise
MSE rate in the regime where $\gamma$ is finite and $n\rightarrow\infty$
(see Tsybakov, 2009). We conjecture that the minimax optimal rates
would be the same for the MISE and pointwise MSE in our ``small $n$''
regime, simply because the trade-off between the polynomial subclass
and the nonparametric subclass exists whether the interest is the
MISE or pointwise MSE.
Second, discussions of related literature in Section \ref{sec:Introduction}
indicate that the classical rate $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$
is an underestimate of the MISE for local smoothing methods such as
kernel density estimators and local polynomials when $n$ is not large
enough. For this problem, we could consider (\ref{eq:model}) where
$X_{i}=\frac{i}{n}$ for $i=1,...,n$ and $\left\{ \varepsilon_{i}\right\} _{i=1}^{n}$
satisfies the assumptions in Corollary 2.3 of Tsybakov (2009). This
setup is simpler than the one considered in this paper, but serves
a good starting point. Like how we establish the results in this paper,
we would first show the minimax lower bound under the ``small $n$''
regime, and then show that the MISE of a local smoothing method has
an upper bound that matches the lower bound up to some universal constant
independent of $n$ and $\gamma$. The proofs would be different from
the ones in this paper. There is some theoretical evidence (although
not a proof) suggesting that it would require a large $n$ for higher
order local polynomials to become beneficial; for example, Tsybakov
(2009) requires the smallest eigenvalue associated with the local
polynomials to be bounded away from zero (Assumption LP1) to establish
the upper bound $\left(\frac{1}{n}\right)^{\frac{2\gamma+2}{2\gamma+3}}$.
This eigenvalue condition in Tsybakov (2009) requires a large enough
$n$ and a sufficient condition given in Tsybakov (2009) is that $n\rightarrow\infty$.
Third, our results prompt a hard question of whether a practical estimator
can be developed to \textit{adapt to the phase transition} shown in
this paper. Cross validation is one possibility as discussed in Section
\ref{subsec:Mean-integrated-squared}. In the literature, an alternative
construction of adaptive estimators uses the Lepski's method; see,
for example, Chen et. al (2021) where the unknown degree of smoothness
is assumed to be fixed while $n\rightarrow\infty$. Hence, the construction
of smoothness degrees in Chen et. al (2021) does not depend on $n$.
Chen raises an interesting point: a better construction of smoothness
degrees should depend on $n$, based on our results in this paper
(personal communication, October and November 2022). However, it is
not clear if this approach will yield an estimator that automatically
\textit{switches} the degree of smoothness to adapt to the phase transition
in the rates, which, after all, is a nonlinear phenomenon.
\newpage{}