Nearest-Neighbor Sample Compression: Efficiency, Consistency, Infinite Dimensions
We examine the Bayes-consistency of a recently proposed 1-nearest-neighbor-based multiclass learning algorithm. This algorithm is derived from sample compression bounds and enjoys the statistical advantages of tight, fully empirical generalization bounds, as well as the algorithmic advantages of a faster runtime and memory savings. We prove that this algorithm is strongly Bayes-consistent in metric spaces with finite doubling dimension -the first consistency result for an efficient nearest-neighbor sample compression scheme. Rather surprisingly, we discover that this algorithm continues to be Bayes-consistent even in a certain infinitedimensional setting, in which the basic measure-theoretic conditions on which classic consistency proofs hinge are violated. This is all the more surprising, since it is known that k-NN is not Bayes-consistent in this setting. We pose several challenging open problems for future research.
This work develops a compression-based algorithm for multiclass learning; the authors claim the method is both efficient and strongly Bayes-consistent in spaces of finite doubling dimension. They also provide one example of a space of infinite doubling dimension with a particular measure for which their method is weakly Bayes consistent, whereas the same construction leads to inconsistency of k-NN rules. Overall, I think this paper is technically strong and seems to develop interesting results, but I have a few concerns about the significance of this paper which I will discuss below. If the authors can address these concerns, I would support this paper for acceptance.
Detailed comments:
I did not check the proofs in the appendix in detail but the main ideas appear to be correct. My main comments are on the efficiency of the method (which I expect the authors can easily address) and on the significant of the results in infinite dimensions.
(I) I have a question about the efficiency of the algorithm:
It is claimed that the complexity of Algorithm 1 is $O(n^4)$. I can see that the for loop traverses a set $\Gamma$ of cardinality at most $O(n^2)$, and in line 5 of the algorithm we pay at most $O(n)$ (which globally yields $O(n^3)$). What is the cost of constructing a $\gamma$-net? Is this $O(n^2)$, and if so, what is the algorithm for doing this? I do not yet believe the efficiency claim by the authors until this part is explained.
It is absolutely necessary that Algorithm 1 is efficient, as otherwise one can just turn to standard $k$-NN methods (not based on compression) in order to obtain the same results, although through different methods.
(II) Infinite dimensions:
It is not clear to me why the results/discussion related to finite dimensions is significant.
If I understand correctly, the results of Cérou and Guyader state that, for a particular (realizable) distribution, no $k$-NN learner (where $k$ grows with $n$ in the appropriate way) is Bayes-consistent. Thus, for a particular distribution, $k$-NN fails to be Bayes-consistent. But perhaps it succeeds for other realizable distributions satisfying equation (3). I can see that in the line after Theorem 3, the authors *seem to* claim that in fact the paper of Cérou and Guyader implies that *any* (realizable) distribution satisfying equation (3) will cause $k$-NN to be Bayes inconsistent; am I correct in this interpretation of Line 221? If so, is this easy to see from Cérou and Guyader's paper?
On the other hand, the authors show that for a particular metric space of infinite doubling dimension and for a particular realizable distribution, KSU is Bayes-consistent. This is interesting provided that $k$-NN fails to be Bayes consistent for all constructions satisfying equation (3), but it is not interesting if the point is simply that, for the Preiss's construction, $k$-NN is not Bayes consistent while KSU is.
It is therefore critical if the authors clarify the extent to which $k$-NN fails to be Bayes consistent (is it for all constructions satisfying equation (3) or just for Preiss's construction?).
Also, the authors should mention Biau, Bunea, Wegkamp (2005), ``On the kernel rule for function classification'', because the paper of Cérou and Guyader (near the top of page 13 therein, or page 352 from internal numbering) claims that Biau et al. also show a nearest neighbor-type method that is weakly Bayes consistent in a space of infinite dimension. Mentioning this result (slightly) weakens the force of the authors' results in infinite dimensions.
Minor comments:
Lines 78-80: How do the authors know about the key motivation behind [15, 23, 16]?
Line 277: I think $n(\tilde{\gamma})$ should be replaced by $n(\gamma)$.
In the 3-point proof sketch of Theorem 2, from lines 262-281:
The paper would benefit from a more explicit/longer explanation part 3.
UPDATE AFTER REBUTTAL
I am satisfied with the authors' responses and recommend acceptance. Also, regarding the confusion about the citations, I'm happy the authors were able to straighten out which paper was actually intended, while also pointing out the disadvantages of the approach from the older paper.