Nearest neighbor pattern classification
Cover and Hart proved that the rule answer as the closest example does errs at most twice as often as the best possible classifier.
Why it matters
A method with no training at all got a proven quality bound, the reference more complex models have been compared against since.
The rule has no training stage: it keeps every example and answers by the nearest one. The paper shows that with an infinite sample the error does not exceed twice the Bayes rate. That bound made nearest neighbour a required baseline and remains an argument for simple methods.