How Low Can Classification Error Go? The Cover–Hart Bracket on the Bayes Error, Its Exact Inverse, and Why Finite-Sample Nearest-Neighbour Error Makes the Lower Bound Unreliable: Evidence From Three Recognition Benchmarks

The Bayes error is the lowest error any classifier can reach on a problem. If it were known, a team would know when to stop improving a model. A classic route to it is the Cover–Hart inequality, which brackets the asymptotic error of the 1-nearest-neighbour rule between the Bayes error R* and 2R* − M R*²/(M − 1) for M classes. I give a complete proof of the pointwise inequality behind the bracket, derive its exact inverse R* ≥ c(1 − sqrt(1 − R/c)) with c = (M − 1)/M, and test the resulting plug-in lower bound on three UCI benchmarks with their official splits: letter recognition (26 classes), optical digits and pen digits (10 classes). Test errors of 1-NN are 0.0435, 0.0200 and 0.0226, giving plug-in lower bounds of 0.022, 0.010 and 0.011. The best of four classifiers reaches 0.0275, 0.0200 and 0.0186, so the bracket looks tight. It is not trustworthy. Learning curves show 1-NN error still falling as a power of the training size, from 0.160 to 0.0435 on letters as the sample grows eightfold, and a fitted power law puts the limiting error near zero for letters and optical digits. The bound needs the limiting error, and the finite-sample error overstates it. For both digit sets the test writers differ from the training writers; within-writer cross-validated 1-NN error on pen digits is 0.0056, a quarter of the test error, so the test error mixes Bayes error with distribution shift. The plug-in Cover–Hart lower bound should not be reported as a floor on achievable error.