I just want to know the reason why the curse of dimensionality mostly affects the non-parametric approaches compared with parametric ones.
$\begingroup$
$\endgroup$
6
-
5$\begingroup$ Reference, please $\endgroup$– DaveCommented Oct 19, 2021 at 0:06
-
$\begingroup$ @Dave from the book An Introduction to Statistical Learning with Applications in R, I quote "When the number of features p is large, there tends to be a deterioration in the performance of KNN and other local approaches that perform prediction using only observations that are near the test observation for which a prediction must be made. This phenomenon is known as the curse of dimensionality, and it ties into the fact that nonparametric approaches often perform poorly when p is large" $\endgroup$– olad uhgCommented Oct 19, 2021 at 0:32
-
1$\begingroup$ Could you please edit that (useful!) information into the original question? $\endgroup$– DaveCommented Oct 19, 2021 at 0:37
-
1$\begingroup$ Here's an intuitive explanation: A parametric method has a constrained solution set. So adding new dimensions increases the amount of solutions much less than for non-parametric methods, which in turn makes them less prone to the curse of dimensionality. $\endgroup$– drmaettuCommented Oct 19, 2021 at 7:47
-
1$\begingroup$ Rather than nonparametric it would be slightly better to refer to constrained vs. unconstrained models. There are parametric methods that suffer the curse of dimensionality, e.g., a regression model with all possible two-way interactions. $\endgroup$– Frank HarrellCommented Oct 19, 2021 at 12:34
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
I like the intuitive answer given by @drmaettu and want to give another, in my opinion, heuristic, and intuitive answer. Suppose that $X_1, X_2, \dots, X_n$ forms an independent and identically distributed sample from some $d$-variate probability distribution with unknown density $f$. The objective is to estimate $f$ based on the observed sample.
If we just assume that $f$ is, say, twice continuously differentiable, all information about the shape, curvature, etc. of the function has to be deduced from the sample. A good estimate thus requires the space to be adequately populated as we know essentially nothing about the function. However, the number of required data points to adequately populate a space increases exponentially with the number of dimensions.¹
On the other hand, if we assume that $f(x) = (2\pi)^{-\frac{d}{2}}\exp\left(-\frac 12\Vert x-\theta\Vert_2^2\right)$, where $\theta\in\mathbb R^d$ is unknown, then we effectively know how the function looks like at every point $x\in\mathbb R^d$ with regard to its shape, curvature, etc. That is, much less information has to be deduced from the sample.
Consequently, the optimal rate of convergence of nonparametric estimators depends on $d$, while the rate of optimal rate of convergence for parametric estimators is $\mathcal O(n^{-\frac12})$.
¹ Consider, for instance, the unit interval $[0,1]$. Let's assume why we fix a grid of 100 evenly spaced points in $[0,1]$. To ensure a maximum distance between two adjacent points in the unit square $[0,1]^2$ would require a grid with 100² evenly spaced points. In the unit cube $[0,1]^3$ a grid with 100³ evenly spaced points would be necessary to ensure a maximum distance of 0.01 between two adjacent points.
