In section 2.3 of Elements of Statistical Learning when the text introduces the linear model and k-nearest-neighbour it states:
The linear model makes huge assumptions about structure and yields stable but possibly inaccurate predictions. The method of k-nearest neighbors makes very mild structural assumptions: its predictions are often accurate but can be unstable.
What is the meaning of stability in this context? Please elaborate in relation to the aforementioned methods.
The book Elements of Statistical Learning does not seem to give a formal definition of the concept of "stability" as it is used in this context. The words stable or stability do not occur in the index. However, the following quote seems to indicate the intended meaning (page 16 of second edition):
The linear decision boundary from least squares is very smooth, and apparently stable to fit. It does appear to rely heavily on the assumption that a linear decision boundary is appropriate. In language we will develop shortly, it has low variance and potentially high bias. On the other hand, the $k$-nearest-neighbor procedures do not appear to rely on any stringent assumptions about the underlying data, and can adapt to any situation. However, any particular subregion of the decision boundary depends on a handful of input points and their particular positions, and is thus wiggly and unstable-high variance and low bias.
With the linear model all of the data contributes to the predictions for any particular $x$. This gives low variance, hence its predictions can be stable — but high bias if the linear model is not a good approximation.
With the $k$-nearest neighbors method, for any particular $x$ only the $k$-nearest neighbors contribute to the prediction. As a result the variance is higher, hence its predictions can be unstable — this is especially so if $k$ is much smaller than $n$.The gain is that by only using close points, the approximation could be better, so potentially lower bias. One problem is that if the ambient space of the $x$ is high-dimensional, there might be no really close neighbors anyhow.
Furthermore, for defining neighbors we need a distance measure, a metric. The results of $k$-nearest neighbors depends critically on the definition of the metric, while the linear model does not use such information. The book elements of statistical learning do assume an euclidean metric, bit other choices are of course possible. For the euclidean metric to be meaningful, the different variables must be on comparable scales. If, for instance, you multiply one of the variables by 1000 (changing unit from km to m, for instance) that will change, maybe drastically, the $k$-nearest neighbors solution, while it has no impact on the linear model at all.
Below is the original answer — as historical documentation:
In this context it probably means that when the input data $x$ changes a little, then the predicted value also changes only a little bit, in an easily understood manner, while with $k$-means, this need not be true, some little change in $x$ could cause a surprisingly large change in the prediction.
I'd like to illustrate these two using the following comparison.
As you can see the higher the variance the more unstable the prediction will be and the higher the bias the mean of the prediction will be more far away from the target. The linear regresson would be stable but its bias sometimes is high(overfitting); while the KNN might be accurate(low bias) but might be unstable(high variance).
