A k-NN validation curve over k = 1 to 200 shows zero training error at k = 1. Which end is high capacity?

## Why k = 1 gives exactly zero training error A k-nearest-neighbour classifier stores the training rows and predicts a new point by looking up its k closest stored rows. When you score it on the very rows it stored, the closest row to each training point is that point itself, at distance zero. With k = 1 the prediction is therefore that point's own label, for every training point. Training error is zero — not because the model is good, but because the scoring set and the memory are the same set. The one caveat worth stating precisely: this holds as long as no two identical feature vectors carry different labels. If the same pixel pattern appears twice in the digit data with two different digit labels, one of them must be wrong at k = 1, and training error is a small positive number instead of exactly zero. ## Capacity runs backwards on this axis At k = 1 the decision boundary is maximally jagged: it wraps individually around every training point, and moving one point moves the boundary. That is the definition of a high-variance, high-capacity fit. As k grows, each prediction is decided by a larger and larger neighbourhood, the boundary smooths, and the fit becomes more rigid. At k = 200 on a modest dataset the model is close to predicting the majority class nearly everywhere — maximum bias, minimum variance. So the plot you get looks like a mirror image of a tree-depth curve. Training error rises with k instead of falling; the train-validation gap is widest on the left; validation error is U-shaped with its minimum somewhere in the middle, and the overfitting region is at small k. ## Why this trips people up Candidates internalise "bigger hyperparameter, more complex model" from depth and polynomial degree, then read every curve left to right as underfit-to-overfit. Applied to a neighbour sweep, that reading is exactly inverted, and the same inversion applies to several common dials: - **Adds capacity as the number grows:** maximum tree depth, polynomial degree, number of leaf nodes allowed, number of hidden units. - **Removes capacity as the number grows:** number of neighbours, minimum samples required in a leaf, minimum samples required to split a node, pruning strength. The safe habit is to name the two ends before interpreting: "left is flexible, right is rigid" or the reverse, written on the plot. Some practitioners plot such dials reversed, or plot an explicit capacity proxy on the x-axis, precisely so every validation curve in a report reads the same way. ## What zero training error is worth Nothing, on its own. A perfect training score is available for free from any model with enough capacity to memorise: a fully grown tree with one row per leaf reaches it too. It carries information only in contrast with the validation branch — the size of that gap is what tells you how much of the fit is memorisation. A candidate who reports "my model gets 100% on training" as a positive result is telling the interviewer they do not distinguish fitting from generalising. ## Reading the neighbour sweep in practice On a digit-pixel sweep the useful part of the curve is the validation branch between roughly k = 1 and the point where it clearly turns upward. Small k values are worth including precisely because they anchor the high-capacity end and make the gap visible; very large k values are worth including because they show you the floor the model degrades to. If validation is still improving at the largest k you swept, the sweep stopped too early and the grid needs extending — the same rule as for any other dial. One boundary worth respecting: the curve tells you which k generalises best on this data. How the k neighbours are combined into a prediction — the voting scheme itself — is a property of the algorithm rather than of the curve, and it is a separate discussion from reading the sweep.