Near-optimal sample compression for nearest neighbors
We present the first sample compression algorithm for nearest neighbors with nontrivial performance guarantees. We complement these guarantees by demonstrating almost matching hardness lower bounds, which show that our bound is nearly optimal. Our result yields new insight into margin-based nearest neighbor classification in metric spaces and allows us to significantly sharpen and simplify existing bounds. Some encouraging empirical results are also presented.
This paper discusses the problem of compressing a set of examples for nearest neighbor (NN) classification. Namely given a set of examples S in some metric space the goal is to output a subset S' of S such that nearest-neighbor labeling of points from S given examples from S' gives the correct labels for all points in S.It is first observed that if points are separated by at least \gamma then any \gamma-net gives a desired set. Together with standard results for doubling dimension this implies an upper bound of (1/\gamma)^ddim(S) on the size of S'. The authors discuss a greedy algorithm for constructing a \gamma-net and also ways to speed it up and further reduce the number of points heuristically.In the second result, that is the main technical result they show that the problem is NP-hard to approximate to within a factor of  2^{(\log (1/\gamma)ddim(S))^{1-o(1)}}. NP-hardness of the problem was known but this is a much stronger inapproximability result. It is obtained via an interesting  reduction from a label cover.Finally the authors demonstrate the performance of 1-NN after their sample compression algorithms on several data sets and compare it with using NN directly. The results show that the algorithm does not affect the error of the hypothesis. This is somewhat strange since Occam razor would suggest that there should be perceptible improvement. In either case smaller sample also speeds up NN classification so applying the compression could be useful.I think that sample compression for NN classification is a natural aspect of this fundamental ML technique and this work makes an interesting contribution to understanding of the problem. Having a nearly optimal lower bound is particularly nice. The techniques are combinations of standard tools and there are no particular surprises here. The paper is also well-written.Some additional comments:line 139: agnostic learning is defined for a class of functions. What you describe is just a basic setup for binary classification from iid examples.line 240: I do not see a definition of c (the weight)Sec 2: it would be useful to discuss whether the problem remains hard in the Euclidean spaceline 362: you suggest that ddim(X) is larger than ddim(S). This does not seem clear to me.