# curse of dimensionality & nonparametric techniques

I have seen it many times in a number of articles that nonparametric techniques are subject to the curse of dimensionality, which may lead to the failure of these methods. Why does this happen? Could give me an example? Thanks!

Imagine that effects aren't additive. Imagine we only have to worry about two values of each predictor, $x_i =$ Low and $x_i =$ High. Then there'd be $2^p$ values our function would need to provide estimates for. In practice, there are more than two values in each dimension to worry about.

http://en.wikipedia.org/wiki/Curse_of_dimensionality

• Thanks very much. According to your response, I guess we need more data to estimate the unknown parameters or functions. However why is it called curse? Mar 19, 2013 at 8:53
• Because without constraining/regularizing/whatever to dramatically reduce the way that the parameters grow, you can rapidly overwhelm any ability to estimate - there's no point in having 2^40 points if you have 2^60 parameters. More points simply doesn't cut it - even if it wasn't prohibitively expensive, there are all manner of other constraints that will bite (space, time, ...). Hence, for example, the focus in statistics on using additive models (possibly after transformation) with nonparametric methods. Mar 19, 2013 at 8:57

Further to Glen's answer, I think it is nice to think of the problem in terms of the volume/concentration of high dimensional space. Directly from the wikipedia article:

There is an exponential increase in volume associated with adding extra dimensions to a mathematical space. For example, $10^2$=100 evenly-spaced sample points suffice to sample a unit interval (a "1-dimensional cube") with no more than $10^{-2}$=0.01 distance between points; an equivalent sampling of a 10-dimensional unit hypercube with a lattice that has a spacing of $10^{-2}$=0.01 between adjacent points would require $10^{20}$ sample points.

So basically as the dimension increases, the number of points required to provide the same coverage of space increases exponentially with the dimension.

This means that for non-parametric methods, which rely on there being points locally to base an estimator on, far more points are required as the volume explodes.

The curse is also often considered in terms of computational feasibility of trying to estimate functions in high dimensions, maybe you could look into this if you're still looking for insight.

• I just wanted to add a side comment - from what I've seen, often in non-parametric literature the curse of dimensionality is 'ignored' by assuming that the number of derivatives the target function has grows with the dimension. This obviously is a pretty huge assumption to make. Thanks for the corrections to my fortmatting user603. Mar 22, 2013 at 7:51