Density estimation

The setting of density estimation typically involves a normed space of functions ${\displaystyle ({\mathcal {F}},\lVert \cdot \rVert )}$, a subset of density functions ${\displaystyle {\mathcal {H}}=\{f\in {\mathcal {F}}:f\geq 0,\int _{\mathcal {X}}f(x)dx=1,\lVert f\rVert \leq 1\}}$ and independent random variables ${\displaystyle X_{1},\dots ,X_{n}\in {\mathcal {X}}\subset \mathbb {R} ^{d}}$ distributed according to the measure with density ${\displaystyle f\in {\mathcal {H}}}$, which generates the data.

Minimax lower bounds are known for different pairs of function classes ${\displaystyle {\mathcal {F}}}$ and comparison metrics ${\displaystyle L}$. Common choices for ${\displaystyle {\mathcal {F}}}$ are:

• ${\displaystyle {\mathcal {F}}=C^{\alpha }({\mathcal {X}}),\alpha >0}$: The space of ${\displaystyle \lfloor \alpha \rfloor }$-times differentiable functions with the highest derivative being ${\displaystyle (\alpha -\lfloor \alpha \rfloor )}$-Hölder-smooth.
• ${\displaystyle {\mathcal {F}}=H^{s}({\mathcal {X}})=W^{s,2}({\mathcal {X}}),s>0}$: The space of Sobolev-smooth functions with square-integrable weak derivatives.
• ${\displaystyle {\mathcal {F}}=B_{p,q}^{s}({\mathcal {X}}),s>0,p,q\in (0,\infty ]}$: The space of Besov-smooth functions.

In fact, the Hölder spaces and the Sobolev spaces are special cases of some Besov spaces, namely ${\displaystyle C^{\alpha }({\mathcal {X}})=B_{\infty ,\infty }^{\alpha }({\mathcal {X}})}$ for ${\displaystyle \alpha \notin \mathbb {Z} }$ and ${\displaystyle H^{s}({\mathcal {X}})=B_{2,2}^{s}({\mathcal {X}})}$.^[7] Thus, it often suffices to derive lower bounds under Besov-smoothness assumptions.

Common choices for ${\displaystyle L}$ are:^[6]

• ${\displaystyle L(f,g)=(f(x_{0})-g(x_{0}))^{2},x_{0}\in {\mathcal {X}}}$: The pointwise squared error (MSE).
• ${\displaystyle L(f,g)=\lVert f-g\rVert _{L^{2}({\mathcal {X}})}^{2}}$: The Mean Integrated Square Error (MISE).
• ${\displaystyle L(f,g)=\lVert f-g\rVert _{L^{\infty }({\mathcal {X}})}}$: The supremum-norm-distance.
• ${\displaystyle L(f,g)=\mathrm {KL} (\mathbb {P} _{f}\lVert \mathbb {P} _{g})}$: The Kullback-Leibler divergence of the distributions induced by ${\displaystyle f}$ and ${\displaystyle g}$.
• ${\displaystyle L(f,g)=\mathrm {TV} (\mathbb {P} _{f},\mathbb {P} _{g})}$: The total variation distance of the distributions induced by ${\displaystyle f}$ and ${\displaystyle g}$.
• ${\displaystyle L(f,g)=W_{\beta }(\mathbb {P} _{f},\mathbb {P} _{g}),\beta \geq 1}$: The Wasserstein-${\displaystyle \beta }$ distance of the distributions induced by ${\displaystyle f}$ and ${\displaystyle g}$.

By Scheffé's theorem, the total variation distance ${\displaystyle \mathrm {TV} (\mathbb {P} _{f},\mathbb {P} _{g})}$ is equivalent to the ${\displaystyle L^{1}}$-distance of ${\displaystyle f}$ and ${\displaystyle g}$.

Smoothness class	${\displaystyle L^{2}(f,g)}$	${\displaystyle W_{\beta }(\mathbb {P} _{f},\mathbb {P} _{g})}$	${\displaystyle \mathrm {TV} (\mathbb {P} _{f},\mathbb {P} _{g})}$	${\displaystyle \mathrm {KL} (\mathbb {P} _{f}\lVert \mathbb {P} _{g})}$
${\displaystyle B_{p,q}^{s}({\mathcal {X}})}$	${\displaystyle n^{-{\frac {2s}{2s+d}}}}$[8]${\displaystyle (p,q\geq 1,\,s>d/q)}$	${\displaystyle n^{-{\frac {s+1}{2s+d}}}}$[9]	${\displaystyle n^{-{\frac {s}{2s+d}}}}$[8]	${\displaystyle n^{-{\frac {2s}{2s+d}}}}$
${\displaystyle L^{2}(\mathbb {R} )}$	${\displaystyle n^{-1}}$[10]	-	-	-

Kernel density estimators, for instance, achieve the lower bound w.r.t. the MISE under a Sobolev hypothesis class under an appropriate bandwidth choice and is thus minimax optimal.^[6]

Regression

In the regression setting, the data arises in pairs ${\displaystyle (X_{1},Y_{1}),\dots ,(X_{n},Y_{n})}$. Assuming that the data is independent and identically distributed, and ${\displaystyle \mathbb {E} [|Y_{1}|]<\infty }$, one can always write$${\displaystyle Y_{i}=f(X_{i})+\varepsilon _{i},}$$with ${\displaystyle f(x)=\mathbb {E} [Y_{1}\mid X_{1}=x]}$ being the regression function to be estimated and a noise variable ${\displaystyle \varepsilon _{i}}$ fulfilling ${\displaystyle \mathbb {E} [\varepsilon _{i}]=0}$ and ${\displaystyle \mathbb {E} [\varepsilon ^{2}]=\sigma ^{2}>0}$. Typically, the independent variables ${\displaystyle X_{i}}$ are assumed to have values in the unit cube ${\displaystyle [0,1]^{d}}$ and to be either determinsitic points on a grid (deterministic design) or uniformly distributed (random design). Thus, ${\displaystyle {\mathcal {X}}=[0,1]^{d}\times \mathbb {R} }$.

The above setting applies to binary classification as well. In that case, the observations take only two values, say 0 and 1, such that ${\displaystyle f(x)=\mathbb {E} [\mathbb {1} _{\{Y_{1}=1\}}\mid X=x]=\mathbb {P} (Y_{1}=1\mid X=x)}$ and given an estimator ${\displaystyle {\hat {f_{n}}}}$ of ${\displaystyle f}$, the classifiers are assumed to have the form ${\displaystyle C(x)=\mathbb {1} _{[1/2,1]}({\hat {f_{n}}}(x))}$, that is, they classify a point as 1 if the estimated probability of ${\displaystyle Y=1}$ is greater than ${\displaystyle 1/2}$ (and 0 otherwise). Indeed, many classification methods are of that form, for example logistic regression, linear discriminant analysis, quadratic discriminant analysis, and k-nearest-neighbors, and support vector machines.

Then, for the statistical analysis, the hypothesis class is of the form ${\displaystyle {\mathcal {H}}=\{f\in {\mathcal {F}}:\lVert f\rVert \leq 1\}}$ for some normed space of functions ${\displaystyle ({\mathcal {F}},\lVert \cdot \rVert )}$ and expectations ${\displaystyle \mathbb {E} _{f}}$ are taken with respect to the joint distribution of ${\displaystyle X}$ and ${\displaystyle Y}$ (or just ${\displaystyle Y}$ if the ${\displaystyle X_{i}}$ are deterministic).

In nonparametric regression, common choices for ${\displaystyle {\mathcal {F}}}$ are:

• ${\displaystyle {\mathcal {F}}=C^{\alpha }([0,1]^{d}),\alpha >0}$: The space of ${\displaystyle \lfloor \alpha \rfloor }$-times differentiable functions with the highest derivative being ${\displaystyle (\alpha -\lfloor \alpha \rfloor )}$-Hölder-smooth.
• ${\displaystyle {\mathcal {F}}=W^{k,q}([0,1]^{d}),k\in \mathbb {N} ,q>d}$: The space of Sobolev-smooth functions with ${\displaystyle L^{q}}$-integrable weak derivatives.

Common choices for ${\displaystyle L}$ are:

• ${\displaystyle L(f,g)=(f(x_{0})-g(x_{0}))^{2},x_{0}\in [0,1]^{d}}$: The pointwise squared error (MSE).
• ${\displaystyle L(f,g)=\lVert f-g\rVert _{L^{p}([0,1]^{d})},p\in [1,\infty )}$: The ${\displaystyle p}$-th norm.
• ${\displaystyle L(f,g)=\lVert f-g\rVert _{L^{\infty }([0,1]^{d})}}$: The supremum-norm-distance.

Under certain technical assumptions, the following lower bounds are known.

Smoothness class	${\displaystyle (f(x_{0})-g(x_{0}))^{2}}$	${\displaystyle L^{p}([0,1]^{d})}$	${\displaystyle L^{\infty }([0,1]^{d})}$
${\displaystyle C^{\alpha }([0,1]^{d})}$	${\displaystyle n^{-{\frac {2\alpha }{2\alpha +d}}}}$[6] (determ. design)	${\displaystyle n^{-{\frac {\alpha }{2\alpha +d}}}}$[6][11]	${\displaystyle (\log n/n)^{\frac {\alpha }{2\alpha +d}}}$[6][11]
${\displaystyle W^{k,q}([0,1]^{d})}$	-	${\displaystyle n^{-{\frac {k}{2k+d}}}}$[11] ${\displaystyle ({\sqrt {n}}/\sigma \geq 1)}$	${\displaystyle n^{-{\frac {k}{2k+d}}}}$[11] ${\displaystyle ({\sqrt {n}}/\sigma \geq 1)}$

Some local polynomial estimators are minimax optimal w.r.t. ${\displaystyle L^{2}}$ under ${\displaystyle {\mathcal {H}}=C^{\alpha }([0,1]^{d})}$ for arbitrary ${\displaystyle \alpha >0}$ for an appropriate choice of the bandwidth.^[6] kNNs are also minimax optimal w.r.t. the MSE under ${\displaystyle {\mathcal {H}}=C^{2}([0,1]^{d})}$ and w.r.t. ${\displaystyle L^{2}}$ under ${\displaystyle {\mathcal {H}}=C^{1}([0,1]^{d})}$ for an appropriate choice of the number of considered neighbors.^[5]