Consistency of the $k_n$-nearest neighbor rule under adaptive sampling

Thank you for the positive feedback and the suggestions for how to improve the organization of the paper. We have already significantly updated our presentation—hopefully in a good way in terms of readability. We will continue revisions with your suggestions in mind.

To address the remaining questions:

Practical considerations.

It is a good point that nearest neighbor methods are generally poorly-suited for high-dimensional data. High cost of memory and computation can be addressed using data structures like the cover tree (Beygelzimer et. al. 2006), approximate nearest neighbor search such as locality-sensitive hashing (Indyk et. al. 1997), and dataset compression (Kusner et. al. 2014). The high statistical cost coming from the curse of dimensionality is more fundamental; to overcome them requires strong priors about the learning problem.

In any case, the main goal of this paper is more theoretical. We aim to illuminate the specific challenges of learning in the presence of noise in the non-worst-case online setting, show how they can be overcome in the case of this fundamental learning algorithm, and further develop the language and techniques for smoothed online learning.

A positive practical consequence of this work would not necessarily be that the kn-NN algorithm is used more widely. Rather, this work shows the ways in which the worst-case setting can be extremely pathological. Overly-pessimistic algorithms that hedge unnecessarily against worst-case scenarios tend to pay the price of being sample inefficient. We hope that a downstream effect of our contribution to smoothed analysis is that it shows us how to be more optimistic, allowing us to design more sample-efficient algorithms without giving up on performance guarantees.

Choice of $k_n$.

The choice of $k_n$ is not extremely sensitive to the rate $\epsilon(\delta)$. In fact, it does not depend on it at all for our second main result, Theorem 5. For the first main result, Theorem 2, note that we do not need to know the exact rate at which $\varepsilon$ goes to zero, just an upper bound on the order. For example, consider the smoothed adversary of Haghtalab et. al. (2020), where we're guaranteed that $\varepsilon (\delta) < L \delta$ for some constant $L > 0$. In this case, we would not need to know the constant $L$. It is enough to know that the decay rate is linear $\varepsilon = O(\delta)$.

Upper doubling condition.

An example of an upper doubling space is Euclidean space with the standard Lebesgue measure.

Confusion about Example 6.

This example is precisely aiming to illustrate the counter-intuitive behavior of non-i.i.d. data. Yes, the labels are generated randomly. However, because of how the data process decided to choose the next instance $X_n$ after observing all the past data $X_1, Y_1,\ldots, X_{n-1}, Y_{n-1}$, the dataset that one ends up with at the very end does not look random at all. In short, when data is collected adaptively, the sampling procedure itself can create patterns out of pure noise. In statistics, this is also the issue of the “garden of forking paths” (Gelman and Loken, 2013).

Geometric nature of analysis.

The arguments here are indeed very geometric, which is due to the algorithm itself being geometric in nature. The smoothed online analysis for a different learning algorithm (e.g. kernels, neural nets, gradient descent, etc.) would require different techniques. However, we do believe that the ideas and techniques we have developed here would have high transferability and utility to these research questions.

Beygelzimer, Alina, Sham Kakade, and John Langford. "Cover trees for nearest neighbor." Proceedings of the 23rd international conference on Machine learning. 2006.

Indyk, Piotr, et al. "Locality-preserving hashing in multidimensional spaces." Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. 1997.

Kusner, Matt, et al. "Stochastic neighbor compression." International conference on machine learning. PMLR, 2014.

Gelman, Andrew, and Eric Loken. "The garden of forking paths: Why multiple comparisons can be a problem, even when there is no “fishing expedition” or “p-hacking” and the research hypothesis was posited ahead of time." Department of Statistics, Columbia University 348.1-17 (2013): 3.

Thank you for the positive review and for pointing out where the manuscript needs copy editing. We have since improved the organization/exposition of the paper, and will continue to edit it with your comments in mind, to help align the paper’s structure to the reader’s expectation.

Verbosity.

We agree that the passages you pointed out are too meandering. They, and many others, have undergone heavy revision. Hopefully we have managed to strike a better balance between being formal/technical and human-readable.

Connection between Section 3 and main results.

To study the behavior of algorithms in the noisy but i.i.d. setting, we often rely on uniform law of large numbers (LLN) to argue that noise will tend to average out (e.g. empirical process/VC theory). But, in the worst-case online setting, the uniform LLN holds only for very restricted classes (Rakhlin et. al. 2015); noise doesn’t need to average out in the ways we might expect if we come from the i.i.d. world. This was developed in Section 2 and Appendix A, which show how the uniform LLN breaks down.

However, these failures are in a sense quite pathological: under the uniform domination condition, they almost never occur, as shown in Section 3. This section is basically about the uniform law of large numbers (LLN) in the non-i.i.d. setting for specific function classes. This is later used to control the averaged behavior of noisy labels: does the majority vote over the labels of the kn-nearest neighbors behave “as expected” (at least coming from the i.i.d. perspective)?

The reason that Section 3 seems so decoupled from the main results about kn-NN is because these techniques are likely relevant for more general smoothed analysis for adaptive/online learning, and so we had extracted them out. We agree that re-organization and improved sign-posting will better help the logical flow of the paper.

Examples of upper doubling spaces.

The upper doubling space is a relaxation of the doubling measure space. This includes Euclidean space with Lebesgue measure. More generally, any doubling metric space with the Hausdorff measure is upper doubling. These are all standard metric measure spaces used in geometric measure theory and metric-based learning theory.

Thank you for taking the time to review and providing a lot of detail as to where the exposition and relationship to prior work can be improved. To address your questions:

Relationship to prior work.

One nice way to place results in learning theory is along two dimensions of “data complexity” and “model complexity”. Data complexity refers to how complicated the process generating the data is: from i.i.d. data, to worst-case data from an adaptive adversary. Model complexity refers to how complex the relationship between instances and labels can be: from parametric (Littlestone, VC, etc.) classes, to over-parametrized/non-parametric classes (neural nets, kernel methods, distance-based learning).

The vast majority of work in learning theory considers two extremes (such as non-parametric learning in i.i.d. settings, or online learning with Littlestone classes), leaving the non-worst-case region in between fairly uncharted. There are a few exceptions.

The line of work from Haghtalab et. al. (2020) considers parametric learning with smoothed adversaries, and they are interested in algorithms that attain finite-sample generalization bounds. The line of work from Hanneke et. al. (2021) is about understanding the Pareto frontier of learnability in the limit with respect to data/model complexity. Correspondingly, the types of data processes they study complement their goals: the former impose stronger, quantitative conditions, while the latter impose minimal, measure-theoretic assumptions. These two lines of work were connected by Dasgupta and So, who focused on the 1-NN learning rule in the non-parametric regime and proposed the general class of dominated adversaries interpolating the two (see also their related works).

However, as they restricted themselves to the realizable/noiseless setting, they left open the problem of adaptivity in the presence of noise. Can an adaptive adversary take advantage of noisy labels (and how)? Are stronger constraints on the data process needed for learning? In this work, we illustrate the challenges of online learning in the presence of noise, which do not seem reducible to the noiseless setting. Indeed, new techniques were needed to analyze the noisy setting. Interestingly, we did not need to introduce additional constraints on the data processes (uniform domination was enough), and the standard kn-nearest neighbor rule works out-of-the-box for far more general settings than previously known.

Thus, this work is also of interest in its own right to the non-parametric estimation community, which has classically studied the i.i.d. consistency of nearest neighbor methods.

Clarification on noise.

Dasgupta and So (2024) considered the realizable/noiseless setting where the labels are given by a deterministic function of the instances, $y = f(x)$ where $f : \mathcal{X} \to$ {0,1}. In this work, noise just means that the labels can now be random. Our setting is formally defined in the first paragraph (line 13-20). Using our language, the setting considered by Dasgupta and So corresponds to the case where the conditional mean $\eta(x)$ is either $0$ or $1$ for each $x \in\mathcal{X}$.

Perhaps surprisingly, the existence of label noise introduces a lot of new challenges to analysis (see Sections 2 and 3), which we discuss next.

New techniques and impact.

To study the behavior of algorithms in the noisy but i.i.d. setting, we often rely on uniform law of large numbers (LLN) to argue that noise will tend to average out (e.g. empirical process/VC theory). But, in the worst-case online setting, the uniform LLN holds only for very restricted classes (Rakhlin et. al. 2015); noise doesn’t need to average out in the ways we might expect if we come from the i.i.d. world. We develop this in Section 2 and Appendix A, which show how the uniform LLN breaks down.

However, we also argue that these failures are in a sense quite pathological: under the uniform domination condition, they almost never occur, as shown in Section 3. We’ve decoupled these techniques from the main results for kn-NN, since they are likely relevant for more general smoothed analysis for adaptive/online learning.

There were other technical novelties that may be of more specific interest depending on the researcher (e.g. Lemma 17 - coupling technique for analyzing dominated processes, Lemma 18 - reduction to smoothed processes, Lemma D.1 - control over long-term kn-NN influence, Lemma D.4 - control over distances to the kn-NN).

Improved proof sketches.

Thank you for pointing out where we should bolster our proof sketches. We will also make sure to include more details in some of our proofs (especially in Theorem 5). Regarding Theorem 5, the main proof can be summarized with the following steps

1. We observe that our data sequence can be thought of as a sequence generated from a Lipschitz dominated adversary combined with an arbitrary adversary (with the arbitrary adversary only outputting during a small fraction of the times).

2. We then note that $k_n$ nearest neighbors run purely over the Lipschitz adversary immediately satisfies consistency due to our prior results about consistency. In particular, this is a case where a regular sequence $(k_n)_n$ will satisfy the conditions needed for consistency outlined above.

3. We bound how often the points from the arbitrary adversary “pollute” the nearest neighbors of our sequence (thereby impacting the consistency in 2). The key idea here is to note that consistency in 2 holds with a margin for almost all points (i.e., the fraction of nearest neighbors that are correctly labeled is above 1/2 with a margin), and thus changing the output of nearest neighbors requires a fraction of the neighbors actually coming from the arbitrary adversary.

4. We bound the number of instances where a fraction of its nearest neighbors come from the arbitrary adversary. To do so, we apply the techniques from Dasgupta and So (2024) that they applied for their long-term influence bound. The main technical challenge here is to extend a bound on the frequency that a set of points forms a 1-NN to a bound on the frequency of a set of points comprise a fraction of points of the $k_n$ nearest neighbors. This is resolved through technical Lemma 19.

Thank you for the careful review and positive feedback. We agree with all of your suggestions. We have since improved the organization/exposition of the paper, and we will deepen the related works section. To briefly address it here:

Relationship to prior work.

One nice way to place results in learning theory is along two dimensions of “data complexity” and “model complexity”. Data complexity refers to how complicated the process generating the data is: from i.i.d. data, to worst-case data from an adaptive adversary. Model complexity refers to how complex the relationship between instances and labels can be: from parametric (Littlestone, VC, etc.) classes, to over-parametrized/non-parametric classes (neural nets, kernel methods, distance-based learning).

The vast majority of work in learning theory considers two extremes (such as non-parametric learning in i.i.d. settings, or online learning with Littlestone classes), leaving the non-worst-case region in between fairly uncharted. There are a few exceptions.

The line of work from Haghtalab et. al. (2020) considers parametric learning with smoothed adversaries, and they are interested in algorithms that attain finite-sample generalization bounds. The line of work from Hanneke et. al. (2021) is about understanding the Pareto frontier of learnability in the limit with respect to data/model complexity. Correspondingly, the types of data processes they study complement their goals: the former impose stronger, quantitative conditions, while the latter impose minimal, measure-theoretic assumptions. These two lines of work were connected by Dasgupta and So, who focused on the 1-NN learning rule in the non-parametric regime and proposed the general class of dominated adversaries interpolating the two (see also their related works).

However, as they restricted themselves to the realizable/noiseless setting, they left open the problem of adaptivity in the presence of noise. Can an adaptive adversary take advantage of noisy labels (and how)? Are stronger constraints on the data process needed for learning? In this work, we illustrate the challenges of online learning in the presence of noise, which do not seem reducible to the noiseless setting. Indeed, new techniques were needed to analyze the noisy setting. Interestingly, we did not need to introduce additional constraints on the data processes (uniform domination was enough), and the standard kn-nearest neighbor rule works out-of-the-box for far more general settings than previously known.

Thus, this work is also of interest in its own right to the non-parametric estimation community, which has classically studied the i.i.d. consistency of nearest neighbor methods.

Response to question.

On the question of whether we can remove the need to know $\varepsilon$ for the first result Theorem 2. This is an interesting question, which is in part what led to the second result Theorem 5. The latter result does not require rate assumptions on $\varepsilon$, but it achieves this by making use of stronger, but standard, metric assumptions (upper doubling spaces, such as Euclidean space).

For Theorem 2 specifically, note that we do not need to know the exact rate at which $\varepsilon$ goes to zero, just an upper bound on the order. For example, consider the smoothed adversary of Haghtalab et. al. (2020), where we're guaranteed that $\varepsilon (\delta) < L \delta$ for some constant $L > 0$. In this case, we would not need to know the constant $L$. It is enough to know that the decay rate is linear $\varepsilon = O(\delta)$. It would be interesting if we could apply the doubling trick to the decay rate. Although, this would come at the cost of imposing additional restrictions on the sequence $(k_n)_n$ for which the result would apply.