Fast NN Prediction with No Statistical Tradeoff

Fast computation often trades statistical accuracy for speed. In nearest-neighbor prediction, achieving optimal accuracy generally requires the number of neighbors to grow as a root of the sample size, creating a corresponding computational burden even with fast search. This talk shows how bias or variance corrections after data quantization or subsampling, together with black-box fast-search techniques, can retain accuracy while reducing prediction-time computation to O(log n). The analysis explains how much quantization or subsampling is compatible with optimal accuracy. Extensive experiments on large datasets from several domains test these theoretical insights. The talk draws on work with N. Verma and L. Xue.