TDSM 10.27

For an estimator to be effective, the distance between every point and its neighbors has to be on average smaller than a value [math]d[/math]. In 1D, this requires the number of training points [math]n \approx 1/d[/math] points on average.

If the number of features (number of dimension) is p, the minimum distance between 2 points is now [math]d^n \Rightarrow[/math] the model would need [math]n^p[/math] training points. As [math]p[/math] increase linearly, the number of training point increases exponentially.