Online Consistency of the Nearest Neighbor Rule

Thank you for your careful reading of the paper and for your thoughtful comments. To address your comments/questions:

0. On the decision to present the results in more general metric measure space setting over Euclidean space: the main tradeoff we were making was between the benefits of a reader's familiarity with Euclidean space versus being able to precisely disentangle which of the many nice properties of $(\mathbb{R}^n, \ell_2, \nu_\mathrm{Lebesgue})$ are used to show consistency and each step of the proof. Reconsidering, Section 7 would probably benefit from being presented in the Euclidean setting rather than in the more abstract length space; we can improve on this in the revisions.

1. Ergodic domination by itself is not enough to achieve consistency. In fact, Blanchard (2022), which you cite in Question 4, construct an ergodically dominated stochastic process for which the 1-NN rules is not consistent. The process they construct has "convergent relative frequencies" (CRF), which is a stronger condition than being ergodically dominated (but weaker than being uniformly dominated). To get the definition of CRF, replace in our definition of ergodic domination the inequality "$\leq \epsilon(\nu(A))$" by the equality "$= \nu(A)$".

   Intuitively, uniform domination constrains how the sequence of instances is generated, while ergodic domination only constrains how that sequence looks in retrospect. Loosely speaking, the ergodic domination condition is blind to the order in which the points came, whereas the nearest neighbor process depends very much on that order. For that reason, the more relaxed ergodic domination condition doesn't give us enough control over the behavior of the nearest neighbor rule to prove convergence.

   Uniform domination is crucial for us in the step where we show that the nearest neighbor process is ergodically dominated; it seems very difficult to significantly relax the assumption here. We discuss this more in point 4c.

   Lemma D.4 is a fairly unimportant in the overall picture; it allows us to argue that it is enough to construct arguments on bounded metric spaces. The error incurred by "unbounded" instances can be made arbitrarily small.

2. We have clarified the exposition for Section 6. We removed the sketch you mentioned; it was misleading because the point isn't to make the $1/\delta$ to $\log 1/\delta$ improvement.

3. Thanks for this comment; it makes a lot of sense to give Section 6 greater focus.

4. Our work relates to Blanchard (2022) in three ways:

   (a) A direct way is through their negative result mentioned above: ergodic domination is not sufficient to guarantee online consistency of 1-NN.

   (b) These two works ask complementary but distinct questions. Blanchard (2022) takes up a complexity-like concern about characterizing the "minimal" conditions under which learning is possible. Earlier, Hanneke (2021) introduced necessary conditions; Blanchard (2022) shows that they are also sufficient. While 1-NN itself is not consistent under provably minimal condition, a nearest-neighbor-like rule kC1NN is, which is the 1-NN rule with the modification that an instance is discarded from memory once it has been used k times to predict (the "k-capped 1-NN rule"). Our work takes up a more algorithms-like concern, about what happens when the 1-NN rule is used under settings that are not i.i.d., and how to study this.

   (c) Anecdotally, in the process of developing this research, we also discovered a version of the kC1NN algorithm (at this point, we didn't know about Blanchard's work). This was a natural algorithm to consider because it allows us to sidestep the issue of bounding any persisting influence of "hard points", since they are evicted from memory after k hits.

   Actually, the consistency of kC1NN for ergodically dominated processes is fairly straightforward under the earlier machinery we've developed before Section 6. The idea is not unlike Theorem 14, where we approximate the underlying concept $\eta$ by an $\eta_0$ with negligible boundary. The key (but not unique) difference arises when bounding the errors from instances whose nearest neighbors fall in the disagreement region {$\eta \ne \eta_0$}; type (b) mistakes in Theorem 14. For the kC1NN rule, the type (b) error rate by the k-capped nearest neighbor process is at most:

   $k \times \textrm{rate that }$ {$\eta \ne \eta_0$} $\textrm{ is hit by } \mathbb{X},$

   which can be made as small as we like by Lemma 12 as long as the generating process is ergodically dominated. In other words, if the generating process is ergodically continuous at a rate of $\epsilon(\delta)$, then the k-capped nearest neighbor process is also ergodically continuous with a slower rate of $k\cdot \epsilon(\delta)$. In this way, the k-capped nearest neighbor process is "better behaved" than the nearest neighbor process. Caveat: this remained a proof sketch and we never checked all steps.

   In some sense, however, this forgetful modification of 1-NN is somewhat counter-intuitive in the realizable setting (assumed by both papers). Forgetting old data points tends to make sense when the underlying concept class is changing/drifting, but here, the learner receives ground-truth labels that are correct for all time. Our result along with Blanchard (2022) allows us to raise new questions: why should the learner throw away correct data? More precisely, what are natural or realistic adversaries such that the forgetful mechanism is required for consistency? Can we illuminate more clearly how the forgetful mechanism allows the learner to hedge against these adversaries?

Thank you for your careful reading of the paper and for your thoughtful comments. To address your comments/questions:

0. On the technical contributions of this work: while we do owe a great deal to prior work in online learning, nearest neighbor methods, and geometric measure theory (see our references), we did also introduce a few new notions and proof techniques:

   (a) Mutually labeling sets

   (b) Approximations by essentially boundaryless functions

   (c) Uniform absolute continuity and ergodic continuity

   (d) Ergodic continuity of the nearest neighbor process

   For example, (a) and (b) also lead to a new, simple proof of the classic consistency result of 1-NN in the i.i.d. setting. The introduction of (c) bridges two existing parts of online learning that seemed to be unaware of each other (the smoothed online learning setting and the universal optimistic online learning setting; see the related works section). And (d) establishes a basic result about the behavior of the nearest neighbor process, which may be of interest in its own right for nearest neighbor methods in general. And of course, the main contribution on the consistency of the 1-NN rule in much broader settings than previously known is also new.

1. Dasgupta (2012) considered nearest neighbor rules under selective sampling. In this setting, a stream of data $(X_n, Y_n)$ are drawn i.i.d. and presented to the learner, but the true label is not automatically revealed. Rather, the learner decides when to observe the accompanying label of an instance. Unlike the standard 1-NN learner, the data in the selective sampler's memory is not necessarily an i.i.d. snapshot of the world. On the other hand, the stream of test instances are still drawn i.i.d. from a fixed underlying distribution, so this is what we meant when we said that Dasgupta (2012) considered a "non-online setting where the train and test distributions differ"

2. The easier result of consistency for the class $\mathcal{F}_0$ of essentially boundaryless functions extends easily to the k-NN rule. One just needs to argue that eventually all the k nearest neighbors are contained in the same mutually labeling set as the test instance. The k_n-NN rule seems a bit more involved, and we don't have a proof for that. The harder part to extend is our analysis of the nearest neighbor process to the k_n-nearest neighbors process. That is certainly of interest, especially to your next question about learning in the presence of noise.

3. The problem is surprisingly subtle when there is noise. For the noisy setting, we do have a preliminary consistency result for k_n-NN for uniformly dominated processes with the constant label function on the unit interval. One reason why noise may add a seemingly new challenge is that the adversary could "make patterns out of noise". We're happy to say more about this, but it does seem that the noisy setting is not at all an easy extension of the realizable setting, requiring additional insight and techniques.

4. The conjecture you gave also seemed very natural to us; we had tried to further weaken the uniform domination condition. The conjecture turns out to be false (if we understood "mixing" correctly). Blanchard (2022) constructs "mixing" sequences such that 1-NN is inconsistent (more precisely, by "mixing", we mean that the rate that $\mathbb{X}$ hits any fixed measurable set $A$ converges; Blanchard (2022) says that these sequences have "convergent relative frequencies" or are CRF).

   Intuitively, uniform domination constrains how the sequence of instances is generated, while ergodic domination (or the CRF condition) only constrains how that sequence looks in retrospect. Loosely speaking, the CRF/ergodic domination conditions are blind to the order in which the points came, whereas the nearest neighbor process depends very much on that order. For that reason, the more relaxed ergodic domination condition doesn't give us enough control over the behavior of the nearest neighbor rule to prove convergence.

Thank you for your careful reading of the paper and for your thoughtful comments. To address your comments/questions:

0. On the technicality of the writing: thanks for this feedback. We will continue to work on clarifying the exposition.

1. This is a very interesting question. Perhaps the even more "obvious" question is: "why is uniform absolute continuity related to ergodic continuity such that it is included in the assumption?"

   At a high-level, the consistency of an online learner is an ergodic—by which we mean time-averaged—property of the prediction strategy, since it has to do with the number of mistakes the learner makes on average over time. Then, the reformulated question above asks: why do we need to constrain the way that $\mathbb{X}$ is generated in a time-uniform way rather than just a time-averaged way? The answer, in short, is that two processes $\mathbb{X}$ and $\mathbb{X}'$ that look the same on average can have nearest neighbor processes that behave very differently (this can be seen as a corollary of Theorem 2 of Blanchard (2022) along with the classical consistency result of 1-NN in the i.i.d. setting).

   Interestingly, the need for a time-uniform constraint arises for the problem of consistency of 1-NN for all measurable functions. If we restrict ourselves to a smaller class of label functions, we may relax the generative assumptions on $\mathbb{X}$. For example, for essentially boundaryless functions in the class $\mathcal{F}_0$ (see Definition 5), it is enough for $\mathbb{X}$ to be ergodically dominated. And for the class of label functions with positive margin on compact spaces, no assumptions are required on $\mathbb{X}$ for 1-NN to be consistent, which is shown by Kulkarni and Posner (1995).

   In addition to our specific contributions about the behavior of 1-NN and nearest neighbor processes, our introduction of the notions of uniform absolute continuity and ergodic continuity helps fill in the continuum of types of non-worst-case online learning settings we should study (see also the chain of settings in Related Works section).