Summary
This paper considers the consistency (or mistake-bound) of the nearest neighbour rule in the realizable online setting when the instances are not necessarily i.i.d. but drawn from a well-behaved stochastic process. The authors prove that when the underlying stochastic process is uniformly dominated, the nearest neighbour rule is consistent for labeling functions that have negligible boundaries. To prove this they introduce the notion of labeling functions on mutually labeling sets, which they then generalize to labeling functions on upper doubling metric measure spaces. Finally they also give convergence rates for smooth stochastic processes, which is a special case of the uniformly dominated setting considered in the paper.
Strengths
The central question of this paper is very well-motivated and an important question in the online learning literature. The paper manages to address the gap of online consistency of the nearest neighbour rule, and outline various interesting conditions for settings in which nearest neighbours rule is consistent. The paper is also quite well written.
Weaknesses
One comment I have regarding the technical novelty is that the proof techniques in this paper are fairly standard across the literature on online learning and consistency of nearest neighbours. I mention this in case the authors would like to highlight something that is not actually a standard technique. This comment does not affect the score.
1. It seems that the paper only proves results for the $1$-NN setting. See point 2 of the questions section.
2. Section 6 seems to serve expository purposes. See point 4 of the questions section.
Questions
1. The authors mention on line 307 that "Dasgupta (2012) ....... considered consistency for non-online settings...." This seems to be a gross oversimplification. I would like a clarification on this point.
Dasgupta (2012): Consistency of nearest neighbor classification under selective sampling, COLT 2012.
2. Do the proof techniques extend naturally to the $k$-NN setup or the $k_n$-NN setup? This is not immediately clear to me from the paper.
3. Do the proof techniques extend naturally to the agnostic case where there is no underlying labeling function but instead $Z_n=(X_n,Y_n)$ are jointly drawn according to some underlying stochastic process $Z=(Z_n)_{n>0}$? The proof techniques would then boil down to computing mistake bound against the Bayes optimal classifier in this case.
4. I am not sure about the significance of Theorem 14 or Section 6, and would like a clarification on the following point. The notion of consistency for uniformly dominated stochastic processes should straightforwardly imply a notion of consistency for stochastic processes which are dominated by much weaker notions of convergence. I suspect that Theorem 15 can be generalized to stochastic processes which are mixing, and the parameter $\gamma$ can be replaced by some function of the mixing coefficient.
Limitations
The paper does a good job at clearly specifying the assumptions used in the setup, but sometimes does not address settings which are not explicitly considered in the paper. Please refer to the Questions section for clarifications.