The k-Nearest Representatives Classifier: A Distance-Based Classifier with Strong Generalization Bounds

We define the k-Nearest Representatives (k-NR) classifier, a distance-based classifier similar to the k-nearest neighbors classifier with comparable accuracy in practice, and stronger generalization bounds. Uniform convergence is shown through Rademacher complexity, and generalizability is controlled through regularization. Finite-sample risk bound are also given. Compared to the k-NN, the k-NR requires less memory to store and classification queries may be made more efficiently. Training is also efficient, being polynomial in all parameters, and is accomplished via a simple empirical risk minimization process.