Consistency of the $k_n$-nearest neighbor rule under adaptive sampling
Authors: Robi Bhattacharjee
Geelon So
Sanjoy Dasgupta
Venue: NeurIPS 2025 poster ()
Keywords: Smoothed analysis
online learning
non-parametric estimation
consistency
Primary area: theory

Abstract: In the adaptive sampling model of online learning, future prediction tasks can be arbitrarily dependent on the past. Every round, an adversary selects an instance to test the learner. After the learner makes a prediction, a noisy label is drawn from an underlying conditional label distribution and is revealed to both learner and adversary. A learner is consistent if it eventually performs no worse than the Bayes predictor. We study the $k_n$-nearest neighbor learner within this setting. In the worst-case, the learner will fail because an adaptive process can generate spurious patterns out of noise. However, under the mild smoothing assumption that the process generating the instances is uniformly absolutely continuous and that choice of $(k_n)_n$ is reasonable, the $k_n$-nearest neighbor rule is online consistent.

Consistency of the -nerest neighbor rule under adaptive sampling
Robi Bhattacharjee'
Sanjoy Dasgupta²
Geelon So
University of Tübingen and Tübingen AI Center Department of Computer Science and Engineering, UC San Diego
Abstract
the adaptive sampling model of online learning, future prediction tasks can be arbitrarily dependent the past. Every round, adversary selects instance test the learner. After the learner makes a prediction, a noisy label is drawn from underlying conditional label distribution and is revealed to both learner and adversary. A learner consistent if eventually performs no worse than the Bayes predictor. We study the neeaestt neighbor learner within this setting. In the worst-case, the learner will fail because an adaptive process can generate spurious patterns of noise. However, under the mild smoothing assumption that the process generating the instances is uniformly absolutely continuous and that choice of (kn),. is reasonable, the -nereet neighbor rule online consistent.
Introduction
We study binary classification with noisy labels in the online setting where predictions are made using the ki, -nenees neighbor rule (Fix and Hodges, 1951; Cover and Hart, 1967). Let (X, p) instance space equipped with metric, let y {0. 1) be binary label space, and let the labels be chosen by nature, drawn from conditional label distribution defined by 1)
[0. 1}.
77x) = Pr(Y 1|X = x).
In the adaptive sampling model, the label noise is benign, but the sequence of prediction tasks can be adversarial and adapt the sequence of observed labels. For ..2.....
a data- eetta-generatng process with knowledge of the past selects an instance X,, E X',
the learner makes a prediction Y, E 3/,
nature reveals label Yn. freshly drawn from the Bernoulli distribution, Ber(n (x))).
The goal is to make as few mistakes Y, + Y, as possible.
If the learner knew 7), then it should predict the Bayes optimal label Y minimizes the expected error at each time step. But this strategy is not generally possible when is unknown. Still, measure rate is no worse than what is achieved by making the Bayes optimal prediction every round:
((n(X,)) 2 1/2). this
learner against it: learner is consistent if its asymptotic mistake
lim sup N
1 14 Yx) 1(Y; YY, < 0 N
Σ
a.s.
In other words, the learner is asymptotically consistent if its performance in the long run is on par with the best predictor given knowledge of ground-truth label distribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Algorithm The k; -nearest neighbor rule
1: for n === = 1,2....d0 do
2: Receive the instance X,,
3: Predict the majority vote label of the kn nearest neighbors X
X
&n (A) 2
Pn
1/2
Kn
n
k=
4: Observe and memorize the label Y
5:
end for
The learner we consider is the kn -neneessst neighbor rule. memorizes all data sees. To predict on the with instance Xn, it sorts the n - previously memorized data points by distance to X..
X(1) ......... X(m-1)
where x(x)) S p(X,.. X(++)).
and it predicts with the majority vote the labels of the hi nearest neighbors, shown in Algorithm 1. If there are distance ties, then we let the data point that arrived first take precedence. Many other, but not all, tie-breaking mechanisms are reasonable, but let leave those details to Appendix E. While this is not needed, we assume that distance ties almost never occur.
1.1 Consistency of -nerestt neighbor under non-adaptive sampling
For appropriate sequences (kn).. the kn -nearst neighbor rule is consistent generally when the instances are not adaptive to the labels (Chaudhuri and Dasgupta, 2014, and references therein). The instances are usually assumed to be generated by an i.i.d. process, but more general assumption suffices (Kulkarni and Posner, 1995), where each label Y; is conditionally independent of given X,,
Pr(V| -
Here, X - (Xi, (2......... is the sequence of instances and Y = (Y,,...,;;;II. Yet,, is the sequence of labels without Y, Note that this precludes adaptive sampling mechanisms, where the selection of downstream instances can depend on the realization of Y, But under this non- -dn-adaptive setting, the proof of consistency is conceptually straightforward. Say that X' is sufficiently nice metric space and is continuous. There are two key ideas:
(a) If kn w (log n) grows sufficiently fast, then the law of large numbers will always be in effect, so that the empirical conditional means converge to their conditional expectations:
(k)
(x()))
(statistical convergence)
k
(b) If ki = on)) does not grow too fast, then the kn nearest neighbors x((h) converge to X,, By the continuity of 17. the conditional means over the neighbors tend converge:
kn. k
-
(geometric convergence)
By chaining these two limiting behaviors together, obtain a very informal proof that the empirical label frequencies over the kn nearest neighbors eventually converge to vy(,,.. And at this point, the leamer's prediction becomes consistent with the Bayes optimal predictor.
To extend consistency beyond the non-adaptive setting, we will show that both types of statistical and geometric convergence can be achieved under much weaker assumptions.
1.2
Main results
We first show that in the worst-case setting, the hi nearest neighbor rule can fail to consistent. However, at least in our counter-example adversary really needs to select points carefully in

---

X1
X4
Xs
X6
X3
X2
Figure I: The binary search adaptive sampling strategy efficiently finds good threshold when data on the line is labeled by threshold function. However, when the labels are generated by i.i.d. noise, the binary search strategy also generates dataset that is linearly separable (see Example 6). For example, here the existing data Xi...., X5 is separable. By querying a point like X6 between the two classes, the data will continue be separable no matter which label is realized.
order to construct such worst-case sequence. This raises the question: how brittle are such hard constructions? In a recent work, Dasgupta and So (2024) provided an answer for the adaptive but noiseless setting, showing that the 1-nearest neighbor rule is consistent under very mild conditions on the data-generating process. That is, worst-case sequences almost never occur.
This work considers the same question, but in the presence of noise. Is the neerest neighbor rule also generally viable prediction strategy in adaptive settings? Or, does noise pose much harder challenge to learning? To answer these questions, we impose the same, mild condition on the data process introduced by Dasgupta and So (2024). It ensures that process selects from small regions with small probability, generalizing the smoothness condition of Haghtalab et al. (2020):
Definition 1 (Uniform absolute continuity). A data process is uniformly dominated by u for any e > 0, there exists 8 > 0 such that when a measurable set A C X' satisfies v(A) < 8, then:
Vn, Pr (X, E A Xeni Yen) <.
We say that X = =Xx), is uniformly absolutely continuous with respect to u at rate s()). We say that the process is smoothed or L-dominated if e()) < Lb for some constant L 2 1.
For = ((6)-uniformly dominated processes, we show that the kn -eeresstt neighbor rule is consistent when the conditional label distribution 1j is continuous and when kü satisfies for some > 0:
kn = w log E- (n-(o
and k = o()).
(2)
In the case when the data process is L-dominated, we recover the standard condition on kn that is imposed to obtain consistency in the i.i.d. setting, which is that k, = w(log n) and k, = o(n).
Theorem 2 (Consistency of the nearest neighbor rule). Let (X, v) be separable metric space with a finite Borel measure. Let 1 X' + [o, 1] be continuous. Let X be uniformly dominated at rate E()). If kin satisfies (2), then the nearestt neighbor rule consistent almost surely.
While Theorem 2 is already very general, it requires that ry is continuous. The next result greatly relaxes this condition to admit all measurable 17. To achieve this, we impose stronger conditions on the space. The general class of upper doubling spaces was studied by Dasgupta and So (2024), where they showed that 1-NN is consistent for any measurable label function in the realizable setting: Definition 3 (Upper doubling). A metric space (X, p) is doubling with doubling dimension d if every ball Bxx, r) can be covered by 2d balls of radii r/2. A d-doubling space with measure v is upper doubling if there exists e such that for all (xx, r). we have v (B(z, r)) S crd..
We show a corresponding result in such spaces for k. nearest neighbor rule in the noisy, adaptive sampling setting. In fact, it further allows us to relax the condition on )k,)). Theorem 2 required the upper doubling spaces, the following regularity condition suffices, which encompasses most choices practitioner might make, as any sequence of the form k. = n (log n)@ suffices if < < or if = and , >
sequence of k, to satisfy (2), which depends on the rate function, e(6).
Definition 4 (Regular sequence). A non non- decreasing sequence (k,,), ) is said to be regular if grows between k, w(log n) and k. o(n/ log n), and if for all c N. it satisfies lim ken/ kn 1. n-000
Theorem 5 (Universal consistency in upper doubling spaces). Let (km)n be regular sequence, and (X, p. v) be an upper doubling space. Lei X be uniformly dominated by u and q) X - (0, 1] be measurable. Then the k -nearest neighbor rule is online consistent with respect to (X, 1))
3

---

1.3 Related work
Nearest neighbor methods are fundamental non-pain con-parmetrii learning, where for the most part, they are studied in settings with strong statistical independence assumptions (Fix and Hodges, 1951; Cover and Hart, 1967; Stone, 1977; Devroye et al., 1994, 2013; Chaudhuri and Dasgupta, 2014; Hanneke et al., 2020; Györfi and Weiss, 2021). Expanding beyond i.i.d. or stationary processes, Kulkarni and Posner (1995) remove independence assumptions across instances, but still assume that sampling non-adaptive (and thus independent of the labels). This work forgoes making explicit independence assumptions across instances or labels, but rather imposes a 'bounded precision' constraint on the data-generating process that was introduced by Dasgupta and So (2024).
This paper contributes the smoothed non-worst-case analysis of learning, which studies learning settings that are in between i.i.d. and worst- (Rakhlin et al.. 2011; Haghtalab et al., 2020, 2024; Hanneke, 2021; Block al., 2022, 2024; Blanchard and Jaillet, 2023; Dasgupta and So. 2024). Many of the work in smoothed online learning take place in the parametric setting, Our work provides complementary results for the non-parann panaamaaettic setting. Moreover, we provide some initial directions for extending the theory of sequential uniform convergence to the smoothed adaptive setting, taking related but distinct approach to Rakhlin al. (2015).
Learning on noisy and adaptively-sampled data
To illustrate the challenges of learning noisy sequential data, we'll ll first describe example of data-genent gata-generating mechanism that produces data that looks starkly different from what 'expected'; : turns out that an adaptive sampling strategy can make patterns out of random noise (Figure 1).
In the following, an instance sequence is generated via the binary search sampling strategy, while the labels are independent flips of the same coin. As an artifact of the sampling procedure, the data appears to be linearly separable, even though the underlying labeling mechanism is uniform throughout space. Thus, the observable pattern in this case will fail to generalize to future data.
Example (Binary search on noise). Fix E (0, 1). Let X' = [0. 1] and let nι(x) That is, each round, regardless of Xn the label Yn ~ Ber(p) is generated by a coin flip with bias p. Construct (X1, YI,..., XN, YN) as follows. Initialize (Xo, Yo) (0,0). 0). For n I,...,N,
be constant.
-select Xn -x 2n (-1)
ddraw Yn, ~ Ber(p).
A1 time N, data points left of X have the label 0, while those to the right have the label 1.
This idea can be used to construct an adversarial sequence for the kn-nearest neighbor rule. For example, if p > 1/2, the Bayes optimal rule predicts everywhere. But, the k, nearest neighbor rule will predict the suboptimal label 0 for long time on instances queried to the left of XN.
[0. and let labels on X be generated by a Bernoulli distribution Ber(p) where p (1/2, 1). Let (kn)n n be regular. There is an adaptive sampling strategy that generates a data stream for which the knn nearest neighbor rule is not consistent:
Proposition (Inconsistency of kn -NN. Let
N Σ
lim sup N
11
Y
1- 8
a.s.
==1
To statistician trained in the i..dd setting, these examples where 'statistical convergence' fail can be counterintuitive. Example 6, specifically what may be surprising here is the large discrepancy between empirical and expected label frequencies. Let I be the open interval (Xo.NN), Then:
I Y= X.EX
and
EYY =p.
I
I X,EI
This is true even though contains a very large number of points with high probability, when is bounded away from 0 or 1. At first, this seems violate the martingale law of large numbers.
Here's a false proof of convergence: if we carelessly apply Aruma-Hoeffding' 's inequality to the bounded, mean-zero random variables Y, -[(Y)] taken in sequence from the interval I, we would

---

conclude that the deviation between the empirical and expected label frequency must tend to zero. The problem is that the set itself carries information about each Y, so the appropriate martingale difference sequence over which apply -xuma-Hoeffding' s needs to also condition on J. Now, as T and Y; are dependent, the conditional expectation of Y; given is not p. Actually, in this case, XN encodes the first N 1 data points (X1, -i.....N--1. NN-1 -N-1) exactly, and so [E [] = Y,
Still, this does not satisfactorily resolve the difference between the i.i.d. and sequential setting. When X is an i.i.d. process, we can even search for a corresponding worst interval /' with the largest discrepancy between the empirical and expected frequencies; I' is quite dependent on Y. But, because the class of intervals on the line has finite VC dimension, so long as I' contains sufficiently many points, we are guaranteed that the empirical and expected label frequencies will be close (for example, see Theorem 5 of Balsubramani et al. (2019)). This follows from i.i.d. uniform convergence theory, which shows that with high probability, the empirical and expected label frequencies sinultaneously converge for all intervals. For more formal comparison, see Proposition A.1.
can be unsettling that statistical intuition from the i.idd setting does not seem to transfer to the sequential setting. Many processes, such as scientific discovery, take place under the adaptive sampling model: we can think of instances as a sequence of experiments that scientific community performs and labels as the corresponding outcomes. This data-generating process is certainly not i..d., as earlier results inform which experiments are performed next. And so, it is important to understand where the new failure modes that arise with adaptivity come from, and how likely are they to occur. To do so, let's take detour into the conditional mean estimation problem.
3 Online conditional mean estimation
Let (X1, Si,,Y,,..... .Y,...,,Xy Xv. Yv) ) be an adaptively sampled dataset, following the model defined at the start. Even in the sequential setting, the discrepancy between the empirical and expected frequencies is well-understood by standard martingale concentration; by Azuma-Hoeffdinn inequality,
N
Pr
Σ Y
Σ n=1
(X,))
2t
< 2exp(-22NF)
N
1=1
empirical frequency
expected Trequency
But now, suppose that data analyst would like to make finer-grained inferences beyond estimating the average label over the whole dataset. In particular, to define the conditional mean estimation problem, we say that a query is any subset of indices Q C [M], possibly chosen with knowledge of the whole dataset. The data analyst would like to use the conditional empirical frequency fi to estimate the conditional expected frequency TN (Q).
iN (Q)
Y; KEQ
and
IN (Q)
(Xi))
Q
Q
conditional empirical Frequency
conditional expected frequency
We can think of statistically valid queries as those that have strong concentration guarantees showing that these two quantities converge quickly to each other as [Q] grows
Of particular interest to this paper is the spatial query: for any region A and capacity k E [N], it selects for the first & instances that land a fixed region A.
Definition 8 (Spatial query). Let A be measurable and & E [N]. Let (X1, Yı,.... XN, YN) be an adaptively sampled dataset. The spatial query (N,((A) is the query at time N:
(A) {n [N] Xn, E and [An (X, ..)] < k].
When A is a class of measurable sets, let (A) = (QNx(A) : A).
Spatial queries are easily seen to a type label-oblivious query, which turn out be statistically valid. Label-oblivious queries can be sequentially constructed, but the decision to insert into the query must be made before Y, is revealed. Thus, we can apply cruma-Hoeffding' 's to the martingale difference sequence Y, E|Y, X Y, x,) ) to obtain the concentration result in Lemma 10.
As technicality, if [Q] O, let Nux (Q) nn (Q) 0.
5

---

Definition 9 (Label-oblivious query). Let (X1. Yi...., XN. YN) At time N, a query Q с [N] is label-oblivious for all n E [M] the conditional independence holds:
) be an adaptively sampled dataset.
In E Q) IL Yn X1, ,
Xn-
Thus, the decision to include n E Q can be made after X, is revealed, but before Y, is realized.
The following provides a simple concentration bound. Notice that there is factor of that does not appear in the original Azuma-Hoeffone s inequality. This is because the sample size [Q] is adaptive, and so we take a naive union bound over all possible sample sizes. Tighter bounds are possible (Balsubramani, 2014; Zhao et al., 2016), but this is good enough for us.
Lemma 10 (Concentration for label-oblivious queries). Suppose that (X,, Yi,..., XN, KN,Yr YN) is an adaptively sampled dataset and Q is a label-oblivious query such that [Q] S k almost surely. Then:
Pr (Q)x(Q) - TN (2) 2 < cxp (-21Q)
Besides label-oblivious queries, we would also like to study queries that may be somewhat label- dependent. Such queries arise in exploratory or adaptive data analysis, where the question being asked can depend on the observed data. Of course, a good statistical sensibility tells us that the query cannot be overly sensitive the dataset itself: for example, query that cherry picks all instances with the label I should certainly be ruled out. But, some others seem reasonable, at least from an i.i.d. standpoint, like the k-nearest neighbor query for fixed æ. After all, if there are no ties, then for every realization of the k-nearest neighbor query, there is spatial query selecting the same instances:
Definition 11 (k-nearest neighbor ball query). Fix x E X' and & E [N]. Let (X1, VI...,, XN, Yn) be an adaptively sampled dataset. Then:
Let Bg = (B(x, : 2 0} consist of closed balls centered at x. A ball query at æ any:
QN,(BB where B Bz.
that QN,,c(B) selects for the first instances X,, that land in B.
The k-nearest neighbor ball query at a is the adaptive query:
QN.( = Q. (B(x
where r == arg min [lQxa s)) 2 k),
>>0
so QN.x(z) (z) selects for instances in the smallest ball B(x, r) that contains at least & instances.
However, as Proposition 7 shows, even such a seemingly benign form of label-dependency can still over-fit to past data in the worst-case setting. The reason that k-nearest neighbor query is valid in the i.i.d. setting is because uniform convergence holds over the class of balls Bz, which is to say that all ball queries are simultaneously valid: no matter how dependent the ball query is on the dataset, convergence is still guaranteed with high probability. As Proposition A.I shows, we cannot generally expect uniform convergence to hold for B, in the worst-case. However, we show now that these worst-case processes are in sense very rare; under mild constraints, they never oceur.
3.1 Smoothed uniform convergence: concentration for adaptive spatial queries
Let X' have a Borel probability measure v and let A be class of measurable sets. In this section, we provide a basic uniform convergence result for spatial queries over the class AA assuming that the adaptive sampling mechanism is uniform dominated by v.
The idea to prove uniform convergence is simple: suppose that we can approximate AA by a finite collection of sets C, which we will call sandwiching cover. To obtain uniform convergence of A, we show that (a) uniform convergence holds on C, and that (b) the approximation error achieved by C small, which is possible to show using the uniform domination condition. To key to controlling this approximation error is the sandwiching property:
Definition 12 (Sandwiching cover). Let (X, be measure space and let A be a collection of measurable sets. Let 2 0. An a-sundwiching cover of A is collection C of measurable sets such that for all A E A, there exist Ain, Aout. E such that:
Ain C A C Aout
and
u(Anut] \ Amn) < a.
Let Na(a) be the a-sandwich number of A, the size of the smallest a-sandwiching cover of A.

---

The sandwich number for balls centered at point will be particularly relevant:
Lemma 13 (Sandwich number for balls centered at T), Let (X, p)v) be a separable metric space with Borel probability measure. Fix E X and let Bg be the set of closed balls centered at z. Then, for any E [0, 11, the a-sandwich number NB, (a) Noob of B is at most 4/a.
Lemma 14 (Uniform concentration for spatial queries). Let (X1, Yı................... YN.. YN) ) be adaptively sampled dataset on (X. p. v), a metric measure space where v is Borel probability measure. Let A be a family of measurable sets and let 2x,x(A) be corresponding class spatial queries. Suppose that X is ( ((]])))niomm)) dominated. For any p E (0, 1), with probability at least 1 p.
28
Na(a)
AQ E QN.(AA), (Qv(Q) - FN
-
log
Q
2(1Q) E)
whenever satisfies e(a) 1/N and f max 2Va(a)
p ,,²}.
Proof sketch. Let C be a minimal a- a-sandwiching cover of A. that |C| <N((). Union bounding over all queries Q E QN,x(C). we obtain from Lemma that with probability at least - p/2,
1
log k N-alaa)
AQ QN.((C).
(Q) -n2 S V
(3)
2Q
To extend this large-deviation bound the rest of (A), we shall use the fact that every A E A is sandwiched between two elements of C' that are a-close Ain C A C Aout. We just need to ensure that the region Aout \\ Aout does not contain a very large number of points from XsN. There are at most Wo (a)² such difference regions, so it is possible to union bound over them as well: Lemma B. shows that none of these regions contains more than points. The contribution of these points are accounted for by the 21/1Q| term and the slight adjustment to 1/(1Q110)
We instantiate this lemma for the k-nearest neighbor query in Corollary 2 of Appendix B.3.
4 Consistency of ki -nerest neighbor rule for continuous 7]
Here, we will work under the assumption that almost surely no tie- ie-breaking needed for example, when the instance space is Fuclidean space with a measure that is absolutely continuous with respect to the Lebesgue measure. Theorem 2, where ties can exist, proved in Appendix E.
Theorem 15 (Consistency of the kn nearest neighbor rule). Let (X, p. v) be a separable metric space with finite Borel measure. Let n X - [0, 1] be continuous. Suppose that X is uniformly dominated at rate E(ō) and that almost surely there are no distance ties. If k. satisfies (2), then the kn th-nnerest neighbor rule is consistent almost surely.
Proof sketch. Under uniform domination, statistical and geometric convergence hold (Propositions 16 and 18). Then, apply triangle inequality. The proof is in Appendix and is slightly more subtle. O
4.1 Statistical convergence of k; -narest neighbor
In the introduction, we described the statistical convergence of the kn neanest neighbor query the i..d. setting: the empirical label frequencies converge to the conditional expected frequencies,
kn
1
(x((1))
knn
informally speaking. the previous section, Lemma and Corollary 2 prove concentration for -eenerrtee
k, neaarsst neighbor queries for instances Z ~ drawn independently of data set. We use this to show statistical convergence for uniformly dominated process.
Proposition 16 (Statistical convergence of -earestt neighbor). Let (X, p. v) be a metric space
with Borel probability measure. Let X [0, 1] be arbitrary. Suppose that when the sampling
7

---

process is uniformly dominated, no distance ties occur, almost surety. Let (X1, Yi....) be adaptively sampled by an -unjuuiiyyy dominated process and let kin satisfy (2). Then:
Ri
lim
a.s.
To prove this, we extend Corollary by a partial coupling. Consider two parallel mechanisms:
1. Let XI, XN, YN, XN+1) be the adaptively sampled process of interest.
2. Let (X1, Yi..... Xv,, YN. Z) be process that coincides with the first, until the last draw from sampled instead.
X' which point an independent draw Z
We would like to bound the chance that k-nearest neighbor query centered at N is statistically non-convergent. In general, this seems quite challenging, since do not have much control over XN+1 except that it is generated by a uniformly dominated process. However, we are able to bound the corresponding event for Z. The following lemma relates the probabilities of these events:
Lemma 17 (Partial coupling bound), Let DD below be the outcome of an adaptive sampling process that is e(6) Juniffrrly dominated by a probability measure v; and, let D'' be the outcome of an alternate mechanism that replace the last instance by independent draw Z Vi
D (X., XN. YN, NN+1)
and D' (X1, XN,Ya YN,Z). Z).
Let F. be the a a-algebra adapted to this sequence and let E be any F-measurable event. Then:
Pr(E)
S inf E(s) + Pr(E). D
D 850
Proof. Let - oX,,, XN, YN) be the alagebra adapted to the first N labeled data points. As E is F-measurable, the random set A {x E X: (Xi,..., YN,,), x) E E} G-measurable. This is the set of outcomes conditioned on X1, X,,..., YN for which E' happens. For any >> O, we obtain:
Pr(E)
E
E
[1 E A} A}]
E NI
[e(v(A))]
YN
(10) < 6()) - Pr(E),
( Pr (v(A)
applying (i) the law of total expectations, (ii) uniform domination, (iii) the upper bound e(v(A)) by E(s) + ((A(A)) $}. and (iv) Markov's inequality. Optimizing over 0 yields the result. _
Proof of Proposition 16. Fix any >> and time n, define the random variable:
D (X,, Yi...., X, Y, ,, Xn);
which are generated by an =()) uniiformly dominated adaptive sampling process. Define En,e as the event that the empirical and expected conditional frequencies at time have t-large discrepancy:
{
Rm
kn
En,t
((k) n
n(x (1))
2 t
Kn
kn R=
Am
By assumption, k; = w (10g inn We show that:
Pr (En,)) = o (n (n-((1tt) (1te))
As the sum of these probability converges, the Borel-Cantelli lemma (Lemma B.3) implies that the discrepancy exceeds t finitely often, yielding:
kn
An (x((k)
lim sup n-000
(k)
St
a.s.
kn
kn
k=1
k=1
8

---

Letting t go to zero gives the result.
Instead of bounding Pr( Fn,a) directly, we consider parallel process:
= Y1 Xn- 1n Z),
where the first labeled data points generated by the same adaptive sampling process, but where the last instance is independently drawn from v. Lemma 17 shows that for any 8 > 0:
1 Pr(En,))
Pr (E S a(s) + D' D
and so suffices to show that eventually, we can set s so that:
s == (n (1+())
and
D Pr(E) S 5²
since =66) is lower bounded by 6. As there are no distance ties, this follows by our choice of k, and the concentration result for the k, nnaaest neighbor query, Corollary 2, in which we let = s². 0
4.2 Geometric convergence of kn nearest neighbor
The next result shows that when the process is uniformly dominated, then x conditional label frequencies that converge that of X, in the following sense.
(kk)) have
Proposition 18 (Geometric convergence of k nearest neighbor). Let (X, p, u) be a space with a separable metric p and a finite, Borel measure Let n X - [0, 1] be continuous. Suppose that X is uniformly dominated at rate E(8). If kn = o(n), then for any s > 0:
N
kn
lim sup N
Σ 1=1
(x(())
(Xx)) 2 =0 a.s.
N
kn
Proof. Fix 8 >> and B be countable open cover of X by balls B(z,r) with the property:
sup ((23))
[n(x)) 17xx')
Such cover exists by the continuity of and the separability of X. Now, define E,, be the event:
E, there is ball B B such that X,, E B and 3 hn
Lemma B.6 shows that when En occurs, all kn nearest neighbors of X,, must also be close, and so the labels are also s-close:
E, C
max - <
ISkSk
Therefore, to prove the result, suffices to show that for any s > that:
1 1 does not occur] S 8 a.s.
sup
N+
To do so, fix 8 > O and take finite subcover 5 of B of size M that covers all but a 5-fraction of X. Denote the remaining uncovered region by Xs = X' UB. Then, we decompose the event: 1 EE does not occur) < 1 fX,, E X3} + 1 (X, & X's and E,, does not occur). By the uniform absolute continuity of X, only an s-fraction of points can land the remainder:
lim sup N
N
Σ 1(x, E Xs) e
a.S.,
by Lemma B.5. We also have that at any time at most M points can land in ball B E B' containing fewer than kn points. Since ki M.MMn + 0, this contributes nothing to the asymptotic rate:
limsup
1 N N
Σ 1(X, & X' and E,, does not occur) 0 a.s.
The result follows from setting 8 sufficiently small and summing Equations and 5. This proof shows that the geometric convergence of kn nearestt neighbor also holds under a weaker condition implied by Lemma B.5 called ergodic continuity (Definition B.4), introduced in Dasgupta and So (2024). D

---

5 Universal consistency on upper doubling spaces
In this section, we introduce the key technical innovations for Theorem 5, which shows universal consistency of the k2 -nearest neighbor rule in upper doubling spaces. The first idea is to show that there are (random) subsequences of X that are well-behaved, consistency. These sequences appear to be generated by an L-dominated process where e(6) I L5, and the labels seem to be sampled from a continuous label distribution 17o- X - [0, 1]. Moreover, L and yo can be chosen so that these subsequences only fail to capture an arbitrarily small fraction of total instances. In the following, we let I be an indicator process, which is simply a binary process we use to indicate instances in the subsequences X [ = [Xx : In = } and X 1-1 = {Xx: In = 0}. Definition 19 (Indicator process). An indicator process I = (Ia), is a {0. 1]-valued stochastic process. Given another stochastic process X. we say that is adapted to X if II is adapted to the natural filtration of X. We say that I is asymptotically rate-limited by y > 0 if:
which Theorem 2 would imply
N E a.s.
1 N
lim sup
N
1=
Lemma 20 (Reduction to Lipschitz setting). Let v be a probbability measure on X, and 1j :7:4 [0, be measurable. Let X be uniformly dominated by v. For any 0 < < 1/2, there exists >> 0, contimuous map TJo X + [0, 1], and an indicator process Il adapted X such that Il is asymptotically
y-rate-limited, the subsequence X[1 - is L-dominated by v, and m nx[ II) no [x 1]).
However, this by itself is not enough to guarantee universal consistency: points in X [ that are not well-behaved may have undue influence on the predictions if they are often a kn -nearest neighbor of downstream instances. In order to control this, the next lemma shows that points in X [1] have limited impact within the set of k,, -nearest neighbors, as long as X' is upper doubling. In particular, if a significant fraction of the nearest neighbors do come from x( then we would discover them through subsampling. For analysis, we define the following triangular array of indicator variables J == (Jma) mm whose randomness is completely independent of X and Y.
Vm S n,
Juna Ber(1/k.))
(6)
Lemma 21 (Long-term influence bound). Let (X, (,,v) be an upper doubling space and (kin) regular sequence. There exist C1 C2 > O so that the following holds. Let X. be uniformly dominated at rate e()) and T. be an indicator process adapted to X. asymptotically rate-limited by q > 0, and be given by (6). For any ō > 0, the rate that an ll-indicated kin -nearest neighbor is sampled by J is:
lim sup N
Σ N
1
11(3xm
N
(3Xm E (x .......... Im- = <
<7 <7(01 0gg log !) + +E()) a.s.
Proof sketch of Theorem 5. For any fixed > 0. construct I and 17 via Lemma 20, so that no is continuous and TI 7-rated limited. Since we can choose y to be arbitrarily small, we may ignore mistakes made during indicated times L, 1. Instead, we focus on bounding mistakes when I, = 0. On these times, the instance X,, lands in the region where 77 is equal to fuu- And so, applying the same argument used for Theorem 15, we obtain statistical and geometric convergence:
N
kn
1 kn ki
kn
lim sup No000 N
(k)
n ((x()))
+
no - (X,,) = 0.
kmn
n=1
But this time, statistical convergence is in terms of 17, and geometric convergence in terms of 17o, so we cannot apply triangle inequality yet. We also need that the discrepancy between 7 and 77o when averaged over sets of heereet neighbors can also be made to be arbitrarily small most of the time.
Notice that whenever the discrepancy is larger than a constant, then a constant fraction of k; nearest neighbors must be indicated by II. Thus, if we sample from the nearest neighbors using J on such an event, we are likely to detect at least one indicated neighbor. However, Lemma 21 shows that the asymptotic rate of detecting indicated nearest neighbors can be made arbitrarily small: set d ? and let y become vanishingly small. And so, the rate at which this discrepancy is larger than any fixed constant is negligible. This allows us complete the triangle inequality, proving universal consistency of the k, nearest neighbor rule in upper doubling spaces under uniform domination. O
The formal proofs for this section are in Appendix D.
10

---

References
Akshay Balsubramani. Sharp finite-time steraed-llggarthmm martingale concentration. arXiv preprint
arXiv:1405.2639, 2014.
Akshay Balsubramani, Sanjoy Dasgupta, Yoav Freund, and Shay Moran. An adaptive nearest neighbor rule for classification. Advances Neural Information Processing Systems, 32, 2019.
Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Proceed- ings of the 23rd international conference on Machine learning, pages 97-104, 2006.
Moïse Blanchard and Patrick Jaillet. Universal regression with adversarial responses. The Annals of Statistics, 51(3):1401-443 2023.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy as statistical learning. Conference on Learning Theory, pages 1716-1786. PMLR, 2022.
Adam Block, Alexander Rakhlin, and Abhishek Shetty. On the performance of empirical risk minimization with smoothed data. arXiv preprint arXiv:2402. 149887770..14987, 2024.
Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for nearest neighbor classification.
Advances in Neural Information Processing Systems, 27, 2014.
Thomas Cover and Peter Hart. Nearest neighbor pattern classification. IEEE transactions on information theory, 1311222,- 1967.
Sanjoy Dasgupta and Geelon So. Online consistency the nearest neighbor rule. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Luc Devroye, Laszlo Gyorfi, Adam Krzyzak, and Gábor Lugosi. On the strong universal consistency of nearest neighbor regression function estimates. The Annals of Statistics, 22(3):1371-1385
1994.
Lue Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
Evelyn Fix and Joseph Lawson Hodges. Discriminatory analysis, nonparametric discrimination. USAF School of Aviation Medicine, Randolph Field, Texas, Project 21 21-49-004, Report 4, Contract
AD4J(128)-31, 1951.
László Györfi and Roi Weiss. Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces. Journal of Machine Learning Research, 22(151)) 2021.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differ- entially private learning. Advances in Neural Information Processing Systems, 33:9203-9215, 2020.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adver- saries. Journal of the ACM, 1133):1-34, 2024.
Steve Hanneke. Learning whenever learning is possible: Universal learning under general stochastic processes. Journal of Machine Learning Research, 22(130); 2021.
Steve Hanneke, Aryeh Kontorovich, Sivan Sabato, and Roi Weiss. Universal bayes consistency in metric spaces. In 2020 Information Theory and Applications Workshop (ITA), pages 1-33. IEEE, 2020.
Sanjeev R Kulkarni and Steven E Posner. Rates of convergence of nearest neighbor estimation under arbitrary sampling. IEEE Transactions on Information Theory, 4128):1028-1039, 1995.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Sequential complexities and uniform martingale laws of large numbers. Probability theory and related fields, 161:111-153, 2015.
Charles Stone. Consistent nonparametric regression. The annals of statistics, pages 995-620, 1977.
Shengjia Zhao, Enze Zhou, Ashish Sabharwal, and Stefano Ermon. Adaptive concentration inequali- ties for sequential decision problems. Advances in Neural Information Processing Systems, 29, 2016.

---

A Proofs for Section
Proposition (Inconsistency of -n-NN), Let [0.1] and let labels on X' be generated by Bernoulii distribution Ber(p) where p E (1/2, 1). Let (kn)n be regular. There is an adaptive sampling strategy that generates data stream for which the kin -neresst neighbor rule is not consistent:
1-P
lim sup
118
N-000
8
Proof. Define the Lth epoch to be the set of times in N,
Epoch,, = =
2 1},
so that the Lth epoch contains 2 2 time stamps. Define Ry to be the rate at which the learner made Bayes inconsistent prediction during the Lth epoch:
R₁. = 24+1
Σ (Y
BpEchh
Notice that as the lengths of each epoch doubles each time, we have by the end of the Lth epoch:
2
Σ Hpn= Rr.
2
Even if in all the previous epochs, no mistakes were made, that would only reduce the inconsistency rate by half. And so, suffices to prove that:
lim sup Ry 2 1-P p
a.s.
00
To do so, we define the following adaptive sampling strategy, which restarts every epoch:
Initialize: select closed interval [a, b] C X that contains no previous data points, and by change of coordinates, renormalize it to [0, 1].
For the first half of the epoch: run the binary search sampling strategy for 24 rounds on the renormalized interval. At the end, sort the data from this epoch by the usual ordering:
(
(24)
By construction, the first M sorted instances have label O, where:
E [ = (1 p)24.
For the second half of the epoch: exploit the region containing many 0's. Define:
max EEEohh
kn
and
min E Epoch, kn-
Let v be point sandwiched between two segments of data points of size k all labeled 0,
(1- <... < < (i+1) <... < x (1tk)
segment of data points
segment of data points
then by sampling the point consecutively for k,/2 times, we can induce the k nearestt neighbor rule to predict 0 every single time. As there are least [(M k*)/k" such sandwiched points, we can induce at least:
M
k. 2
-
inconsistencies.
T-r
Therefore, in the Lth epoch, in expectation, the rate of inconsistency is at least:
1-= 2k* ) 2
[Rt] 2
2L+I
k*
12

---

Using the regularity of kn, we have that lim ke/k" 1, so that over all the epochs:
(1-p)
lim L+000
E R 2
4
Thus, by apply the martingale law of large numbers on (Rz),. we obtain:
- p)
lup R 2
a.S.,
L-+00
4
which implies the result.
Proposition A.1 (Intervals with large deviation). Two datasets on [0, 1] and y {0, 1) are
generated as follows. The labels have conditional distribution 17(z)) = 1/2 everywhere.
Let (I,, NN, YN) be adaptively sampled by binary search, as defined Example 1. Let (X1, Yi...., X'x, Yk) sampled by a uniform i..d. process on X y
Let I (Xa, Xo. be interval with endpoints chosen uniformly at random from the adaplive dataset. For any & > 0, the empirical frequency and expected frequency are unlikely to similar:
Pr (1 Σ X,EI
77 2
S
Ne
S 2E.
(non-convergence in adaptive setting)
Let l' = (X,, X1)) be an interval with endpoints chosen uniformly at random from the i.i.d. dataset. For any & 0, the empirical frequency and expected frequency are unlikely have large deviation:
Pr
Σ XLEP
Y
2 Ne
S2exp(-2Ne2).
(convergence in i.i.d. setting)
Proof.
1. Non-convergence in the adaptive setting. Sort the dataset generated by Example 6, so
that:
x(1) ... (N)
By construction, the labels are also sorted; there a threshold E (0. where:
yo 1 2
Let I = 1x0,x00) be interval. The discrepancy is therefore given by:
77
it 2
2)
Σ
Y.
k 2
X,EI
It follows that an interval has discrepancy less than Ne and only
i
1
1 Ne
k + 2
Ne, k +
2
2
This occurs with probability at most
2N N
= 2s.
2. Convergence the i.i.d. setting. This follows from Hoeffding's inequality.
13

---

B Proofs for Section 3
B.1 Sandwiching covers
Lemma 13 (Sandwich number for balls centered at x), Let (X, p. be separable metric space with Borel probability measure. Fix X and let Bg be the set of closed balls centered at x. Then, for any E [0, 1), the a-sandwich number Ngg, (a) of Bn is at most 4/a.
Proof. Let X ~ and let F(r be the cumulative distribution function of p(a, X). Let M e N be any number greater than or equal to 1/a. For m 0,. ...... M, define:
min {r 2 0: F(r) 2 m/ m/M),
T'
where I'm exists because is upper cemi-continuous and is possibly infinite. We claim that the following collection of open and closed balls forms an a-sandwiching cover of B...
C
U (B(z, rm), m==
from which the result follows by letting M = 1 1 since 4/a 2 2. 2 +1 [C).
We now choose Am Aout satisfying the a-sandwiching condition for any B(x,r) r) E Bz. Let E (O....,Ay .) be the smallest number such that F(r) S Frmm), which implies:
v u(B((,Tm--)) < v(B(z, r)) s v (B(2,T)))
There two cases:
(a) I = -y, then we let Ain = Aout = B(x,, rm). The sandwiching condition evidently holds.
(b) If Ym then we let Ain = B(I, 11) and Aom. B(x, ). By construction of Tms
(B(rr, s)) < m/M, vs <
By the continuity of measure, we obtain v (B(II, rm)) S m//. By construction of rm-1,
(BB(r (m-1)) (m-1)/M.
It follows that (Aout \ An) & 1/M a.
B.2
Concentration inequalities
Lemma 10 (Concentration for label-oblivious queries). Suppose that (X1, YI...., XN, YN) is an adaptively sampled dataset and Q is a label-oblivious query such that [Q] < k almost surely. Then:
Pr (f (Q) NΙ (Q) 2 t) s 24 exp (-)
Proof. Let To Define TI, T2,.-.; -....-;TK, be the sequence of stopping times:
T, min {t > 7- Q)
where the stopping times are possibly infinite. Thus, is the ith index inserted into Q, and we have:
= (n+ < oc).
We define You 0, so that Y;, = 0 whenever Tæ = oc. Then, for any fixed & < k. the following forms martingale difference sequence:
Y, E [Y=, X,, Y ........ X,,]. where we can let Xoo be defined any deterministic constant.
i 1,..,,,
14

---

Now, we may apply Houma-Hoeffding" inequality, we obtain:
Σ Yr Σ (X,,) 2 S 2exp (-20t²).
Pr
We can union bound over all 1, ,,....h particular for the random sample size [Q),
hi and since [Q] I k almost surely, the bound holds in
[QI
Pr Y
Σ
Σ
(X+) 2 1..111
< 2k exp (-21Q11²).
We obtain the result by a change of notation. Recall that when |Q] > 0,
1
NN (Q)
Y
and (Q) [Q1
(Xx))
Q
EE
iEQ
and that when IQ] = 0, then (Q) = NN (Q) =.
YN) be an adaptively sampled dataset (X, p, v). metric measure space where v is Borel probability measure. Let A be a family of measurable sets and let 2N be corresponding class of spatial queries. Suppose that X. is unnfformly dominated. For any p E (0,1), with probability at least 1 p.
Lemma 14 (Uniform concentration for spatial queries). Let (X,,Y
28
log k &NNaa))
AQ E QN.(AA),
(QN(Q) (2) -
+ V
1Q1
2(1Q1 E)
p
whenever satisfies e(a) = 1/N and l max 2Na(a) 62...
p
Proof. Let C be a minimal a-sandwiching cover of A, so that |C] S Wa(a). By union bound taken over queries Q @N,(CC, we obtain from Lemma 10 that with probability at least p/2,
k: Na(a)
VQ QN,(CC)
(Q) (2) S
log
2
P
To extend this large-deviation bound the rest of (A), we shall use the fact that every A E A is sandwiched between two elements of C' that are a-close Ain C A C Aout. We just need to ensure that the difference region A,, A Aout does not contain a very large number of points from XgN.
To do so, define the collection of difference regions between a-close sets in C:
A,C (AI A,, A2 E C and ((AiAA2) - <a).
There are at most (a)² such regions. We can now apply Lemma B. to show that when X is uniformly dominated, these regions rarely contains more than points. In particular, we take union bound over all a-close pairs of sets in C, so that with probability at least 1 p/2,
YU E A.C,
|nn Se
whenever E 2 max (2log 2Na(a) e² and E(a) = 1/N.
Given A E A. let Ain CA C Aout satisfy the a-sandwiching property. Let Qin = -N. (Ain). It follows that both events (3) and (7) oceur, then:
Σ Y ((x)) = Σ SEQ
Y, x(xi) +
Σ
Y - (Xx)
Σ Y (Xi,)
iEQ..
REQiQI
iEQi 10
k Vaaaa))
< IQQul . V 2/Q
log
+ 2f,
where we use the fact that neither Q \ Qin nor Qin QQ can contain be more than & indices (note that
Qin \ Q can non-empty if reached capacity with some instances falling in A \ An). Dividing
through by [Q] yields the result, where we use 1Qml [Q] and 1/|Qml S 1/([Q) f). L
15

---

Lemma B.1. Let X be E(0)-uniformly dominated by U. Fix N E N and let A be measurable. Then:
Pr Σ EX pp
whenever 2 max log p ea NNy and = E(v(A))
Proof. The probability that X, A is bounded by because X is uniformly dominated. It follows that for any fixed sequence distinct times S 4 < la < ... < by S N, the probability that the event Xe, E A occurs each of these times is bounded by 7f. Formally:
Pr ^ X EA!
<
III
Pr
X E A
A X1 EA
i=1
II E
Pr (X A (et)
A Xe, A ST
(8)
We can bound the event that XgN hits least times by a union bound over all (?) possible sets of time indexes (ti...., tt} for which X E A:
N
Pr
( E A3 2
WVB
Σ
Pr
X1,
EA
(8)
cN
(1)
IA
IV
P.
which follows from (i) the union bound, (ii) Equation 8, (iii) the standard bound (7) $ (eN/e) (iv)
f 2 e² No,, and (v) l 2 log p
B.3
Concentration for k-nearest neighbor query
The following concentration for the k-nearest neighbor query for a random point Z ~ follows directly from Lemma 14, where A is the B2 of balls centered and bound on its sandwich number comes from Lemma 13. A version with tie- he-breaking is given in Appendix E.
Corollary 2 (Concentration for the k-nearest neighbor query). Let XN., YN) be adaptively sampled by an (6)-unifor dominated process. Let Z ~ v be independently sampled. Suppose that almost surely there are distance ties to Z; let x(),
(.., sort the instances:
p x(2))
1Z X(N)).
Let 1,p (0, 1). Suppose that
100
log k: + log
-WIN + log ) Then:
b
Pr
(
Σ j=1
2 Sp.
k
Proof. Since Z is chosen independently from the data, may apply the uniform convergence result Lemma 14 Bz, the closed balls around Z. In particular, when & sufficiently large, then:
4f + log
2
1
NN (a)
k
=
2(k E) log
<t.
t2
k
P
16

---

when and 8 max {2log (N) P
2..
By Lemma 14, with probability least p.
yGI 1 k
E Ex
< t.
j=1
Then, Lemma 13 bounds NB (a) - 4/a. So indeed, & is sufficiently large:
4e + log k
8
log 2 + e² log ht + log 4 + log
1 p
t2
8
1
1
10 log k + log 8-1(1/N) + log
k,
12
p
since log 2 + e² + log 10.
B.4 Technical lemmas
Lemma B.3 (Borel-Cantelli). Let (An)n be a sequence of events such that Σ Pr(An) < cc. Then:
Pr (An occurs infinitely often) 0.
For reference, see Theorem 2.3.1 of Durrett (2019).
Definition B.4 (Ergodic continuity). stochastic process is ergodically dominated by o for any > 0, there exists
such that when measurable set C X satisfies v(A) 6, then:
N
lim sup N
Σ 1{xm E A] <
a.s.
N
We say that X is ergodically continuous with respect to U at rate E(6).
Lemma B.5 (Lemma 5, Dasgupta and So (2024)). Let (X,) be a process that is uniformly dominated by e at rate E()), and let (Fn) be its natural filtration. Let (An)n be (F))x-rreiictabl sequence where lim sup, v( (An) < 5. Then:
N E1xx E An) S E())
lim sup
&.8.
N
N
Lemma B.6 (Closeness of k-nearest neighbors). Let be any process in X and fix some n. E N. Let B = B(2,r) r) be any ball and let 3B denote the larger ball (r2,3r). Suppose that X,, E B and |B Xx 2 k. Then, the k-nearest neighbors of Xn are contained in 3B,
x()
x(k) E 3B.
Proof. For all x E and x' $ 3B, we have:
p(x, Xn) < 2r and p(z,Xn) 2r.
That is, all points in B are closer to X,, than points outside of 3B. Since B contains at least points, the & nearest neighbors X,, must come from 3B.
17

---

C Proofs for Section
Theorem 15 (Consistency of the k,, -neaestt neighbor rule). Let (X, p, vi) be separable metric space with a finite Borel measure. Let yj X - [0. 1] be continuous. Suppose that X is uniformly dominated at rate E(6) and that almost surely there are no distance ties. If kn satisfies (2), then the kn neerestt neighbor rule is consistent almost surely.
Proof. It suffices to show that the rate which the k, nearest neighhor rule does not coincide with the Bayes optimal prediction goes to zero. When ((x,,, 1/2, we say that both possible predictions in y {0, 1} are Bayes optimal. Then, the Bayes-inconsistent event is contained in:
{nn + Y kn
C
Kn E
- 7(Xn) 2 2 0< m(Xx)
1 2
S {
for any > O. By applying the triangle inequality to the statistical and geometric convergence results, Propositions 16 and 18, obtain that:
N
Rn.
limsup N-+00
((s)
(Xx)
2 8 2
=0
a.s.
kin
a
1==1
k=1
Define Ag to be the set:
A.
X
n(2))
S
2
Thus, the rate that kn nnaaest neighbor is inconsistent with the Bayes predictor is bounded by:
lim sup
1 N
Ei{yn
lim
1 N
E1{x, A.) S (v
N
N No000
==1
n=1
where the second inequality holds by the uniform domination condition. The result follows by letting J. which implies that A, 2. By the continuity of measure, v(A.) also converges zero, so by uniform domination, so does e(v(A.)).
18

---

D Proofs for Section
D.1 Proof of Theorem 5
Theorem 5 (Universal consisteney in upper doubling spaces), Let (kn)n be regular sequence, and
(X, p.u) be an upper doubling space. Let X be uniformly dominated by and ni X + [0. 1] be measurable. Then the kn -eenress neighbor rule is online consistent with respect to (X, 17).
and let and ?o be as described in Lemma 20. We show that the asymptotic mistake rate is almost surely bounded by 3y, This implies the result since y was arbitrary.
Proof. Fix y
By construction, the subsequence X(1 T] asymptotically all but a-fractioo of X. And so, if the learner makes a mistake at each indicated time J, = 1, this would contribute at most an additive term of in the overall mistake rate. In the remainder, show that mistakes made during the rest of times, when In = 0, contribute at most another term of 2y,
As in Theorem 15, it suffices to show that the rate which the -nearess neighbor rule does not coincide with the Bayes optimal prediction goes to zero. On a non-indicated time 4, 0, we have that (x,)) (.().). and for any 0, the Bayes-inconsistent event is contained in:
{ + Yy and I,-- }}
and In 1n=0 = for (o(Xx)
c
y
(X))
S s
km
2
Let's bound the rate which either (a) (b) occurs. As no is continuous, may choose 0 such that by uniform domination, (b) contributes at most another y term to the mistake rate:
0 (o() - 2 S Sy
sup sup 000
a.s.
n=1
As for the event (a), we can first bound
Ek= y-!1) - no(
using triangle inequality by:
kn
(Xx+)
+
(Xxx)
(x+) +
no (X(x) no (Xx))
Kn 1=
kn k=
kn A==
ka l=
km
(98)
(sis)
where both (i) and (iii) eventually never exceed 8/3 almost surely, resepetively by statistical conver- gence (Proposition 16) and geometric convergence (Proposition 18). Thus, to bound the rate that event (a) occurs, it suffices bound the rate that (ii) exceeds s/3. This is bounded by the rate that an s/ s/3-fraction of the k -nearett neighbors of X,, come from the region {n * no and thus are indicated instances. To bound this, let A,, indicate the event that Ln but at least an s/ s/3-fraction of the ki -nearest neighbors of X,, are in X[I]. Then, it suffices to show:
N Am=
lim N
=0
a.s.
(9)
N
1=1
To do so, we bound the long-term influence of x [1]. Let Bn be the indicator from Lemma 21:
B, = 3xm E (x.!). ......... ...., x(kk)) Im Jm, =1)
-
the event that some kn -naaest neighbor of X,, comes from X [[1] and is sampled by J. which was defined in (6). By setting = y and sending 7 + 0 as before, Lemma 21 shows that:
N Bn =
lim N N-
a.s.
(10)
n=1
19

---

To complete our proof, we relate A, to B, showing that significant fraction of the k, -nearestt neighbors cannot come from [I] for otherwise they would have been sampled by J. Observe that at time the conditional expectation of B, can be lower bounded in terms of An
Bn Xen] = Pr = E (
x(km)) } In Jm, = 1)
k/3
2 An
kn
1
8/3
An
4
where the last inequality holds for all Kn 2 2. Now, averaging over time, obtain:
4/3
1 N
B
Σ An. n=1
By the martingale law of large numbers and Equation (10), as N goes to infinity, the left-hand side must converge zero almost surely. It follows that the right-hand side must well. This implies Equation (9) and completes the proof.
D.2 Proof of Lemma 20
Lemma 20 (Reduction to Lipschitz setting). Let u be probabilltty measure on X, and 1j X []
be measurable. Let X be uniformly dominated by v. For any < < < 1/2, there exists >> continuous map Tio X + [0, 1}, and indicator process ll adapted to X. such that Il is asymptotically
y-rute-limited, the subsequence X[1 - is L-dominated by v, and 17 (x
II) n (1
Proof. Let pn denote the conditional measure of X,, on X, so that for all measurable X::
pn (A) Pr (X, E A Xeni Men).
Because X is uniformly dominated by v, the measure Hn itself is absolutely continuous with respect to v. Thus, the Radon-Nikody theorem implies that it has density function fn X' - [0, co),
(A( = -f fn(x) v(dx).
Let L ---17 and let A, = fx: fa(x) 2 } By design, X, is unlikely to be drawn from Ans
[-(6/2)
(A() S (A(.)) (1)) E
( Pr
(((()) 2 4)) (aa) X-0
(Z ' (1,((())))
(6v)
y
<
X~.
2
where (i) applics the uniform domination property of pans (ii) rewrites v(An) as a probability, (iii) applies Markov's inequality, and (iv) follows from our choice of L and from the fact that fn is density function, so that Ex-v[fn (X)]
We now also construct the continuous map N/-- By Lusin's 's theorem, there is an open subset B C X continuous. Since X' is a metric space, this restriction can be continuously extended to all of X' using the Tietze extension theorem. Let 1oo be any such extension. Then, X,, is also unlikely to be drawn from B,
with vBB)= < E-! (3) such that the restriction of 7) X'
(B) S (e((B) < 2
Finally, we define the indicator process 1 = (In)xs where:
In = 1 (Xn E An BB.
Since pn U B) S 7, the martingale law of large numbers implics that is 7-rate limited:
N In
lim sup
Σ
S
8.S.,
N N-00
1=1
20

---

proving that condition (1) holds. Condition (3) also follows by construction, since is equal to on X' B. Indeed, when I, then Xn & B. Condition (2) remains.
For this last condition, for any n where I = O, the distribution from which X, is selected is conditioned on the fact that Xn & A, U B. Since A, U B has u-measure at most 7, see that for any measurable set E, the probability that Xa E E' is at most:
Nn (E) (An U UB)
Pr (Xn E Xen: Yen, I 00
1 Pn (An B
$
1 fa(2) 1fx (A, UB) u(dr)
1
/ fn(x) 1(f((t) L/2) v(dx)
JE
E 2 v(dx)
v(E) S Lo(E).
2(1 (1
Here, we exploited the fact outside of the set An. the density fn is at most L/2, and that 7 < 1/2.
D.3 Proof of Lemma 21
Lemma 21 (Long-term influence bound). Let (X, p.v) be an upper doubling space and (kn), a regular sequence. There exist c1. so that the following holds. Let X. be uniformly dominated at rate =(6) and be an indicator process adapted to X asymptotically rate-limited by q >> 0, and be given by (6). For any 5 > 0, the rate that Il-indicated hin -earest neighbor is sampled by I is:
N
lim sup
1
Σ ==1
1
(3Xm E ,x.,)..... X(k,)) Im = =1) < <> +o log 1) + =(() )
a.s.
N -0000
N
The proof this result builds on the technique developed by Dasgupta and So (2024), specifically for their Theorem 17. In Sections D.4 and D.5, review the key definitions from their work along with some modifications to extend to -eaneessst neighbors (rather than 1-nearest neighbors).
We begin with quick technical lemma that lets us bound how many points are likely to be selected for which both I and J are 1.
Lemma D.1. Let and be as defined in Lemma 21. Then:
N LNJnN S 7.
KN N
limsup N
n=1
Proof. It is clear that lim lim sup Σm= In S y almost surely. Thus, for any a there almost surely exists Na such that for all N 2 Na. 4 5 +
Pick any N for which this occurs. Observe that the values of Jn.N are i.i.d Bernuuli variables each with expected value ky. Thus applying Hoeffding's 's lemma over all of them, we see that with probability least 1 exp N(5+a)) ). our desired sum is at most (7 + a) + +
Since (kn)n is regular sequence, Kx grows strietly faster than log n, which implies that ENE exp (- N(++0) is finite. Applying the Borel-Cantelll lemma implies that our deisred sum is
N
KN
most (7 + a1 + a) almost surely completing the proof.
Proof of Lemma 21. Without loss of generality, X' has diameter 1. For < S N, let k(n) be the number of instances < n for which T,JrN 1, and let Tę to be the time of the kth time for which this occurs.
21

---

Next, we construct a chain of sequentially contstrttteec cover trees (Definition D.6) exactly as done in the proof of Theorem 17 in Dasgupta and So (2024). That is, let (Cx)s be chain of sequentially- constructed cover trees associated to the sequence X X X....... Let L denote the insertion rank of X,, For n 2 Tke define
Tk - La
d 8
+GRa(n):
(11)
where (c, d) are parameters associated to the upper doubling condition (Definition 3), and Gk,
the number of generations of children X1, has by time n.
Next, construct a of very small balls that are centered at the points in our cover as follows. Define
<(()
Tn U
cone x Tk,n + 1)
and
An U 2B, BET,
k=1
where the cone is defined as in Definition D.5.
We now relate the number of times in which X, has nearest neighbor with I,Jt,N 1 to events related to this cover tree. Since v is an upper doubling measure, we immediately have that the sequence X1, X2... almost surely distinct points. Thus, applying Lemma D.8, with the combined indicator process InJn,N, we have
N
N
ax2 E ( ....., x((m)) x(hn)))
Σ
SE E2Brit/2
n= B, EC
N
N + Σ 1(,, E An-1). n=1
Σ
Σ
1
==1
B,ECaín 1y\Ta-1
We now bound each term separately. For the first term, apply Lemma D.4 see that
N
N
Σ
(E2B..T/2) S
ΣN
1 F2BB./22
S 2 kN
2 (C \TNl-
B, 1,
B,EC.EN-19 n=1
Bounding the total number of balls within this set follows identically to the proof of Theorem 17 in Dasgupta and So (2024): it suffices to count the number of balls for each instance X,, that are not in
its (Ta.N + -tai::
((N)
(CA(N) \ 1T <
( + 1) LA
(2
N(N)
S <k(N)-
2+ d
Ig
Σ
Gk
1
) *(N).
S <(N)
2+
1g
To bound the second term, Lemma D.10 implies that A,, has mass at most v(An) 8 for all Thus the probability that X, E Ag-1 is at most e(5), and the expected number of total occurrences is (E(8)).
Combining our bounds, fix any a 0. Lemma from Dasgupta and So (2024) implics that for N sufficiently large, Σ 1(X, E An-1) < (e(() + a) with probability 1. Furthermore, by applying Lemma D.I, we see that for N sufficiently large, se(N) probability 1. Combining these, we see that
kx N. (> + a) also occurs with
3X2 (x...... ....,,((..)) x(
x=1
< 22d+1 KN
(7 aa+
Ig c
) + (=(6) +a)
KN
d
$ ( + a222d+1
3+
Ig
+ (8) + a.
d
22

---

Since 0 was arbitrary, it follows that almost surely,
lim sup N
Σ 1=1
NV
13x, aX2 E ( ...., x...,.x(.) x(h11))
1 722d+1
3
lg [ d 8 ) + =(6).
N
D.4 Packing Bounds
Here we include several definitions that taken directly from Section 1. of Dasgupta and So (2024). In some cases, we include slight modifications that will prove useful for generalizing their results from 1-nearest neighbor to kn neaaret neighbors.
Definition D.2 (Packing number, Definition 18 Dasgupta and So (2024)). Let > A set Z C X is an r-packing if all of its points bounded away from each other by distance r,
inf 2,z'EZ
='z,
The r-packing number P.( of U is the maximum possible size of an r-packing Z contained in U.
Similarly to Dasgupta and So (2024), we will use packing numbers to bound the number of times point has large k, -earest neighbor radius (its furthest neighbor is quite far from it). To do so, we adapt their notion of an "r-separated event" (Definition 19 in Dasgupta and So (2024)) to apply to k, -nearest neighbors. An r-separated event visualized Figure 2.
Definition D.3 (r-separated event). Let X be a process, > 0, and (kn)n be a sequence. The r-separated event at time n. is the event E that Xn has distance at least from its hi nearest neighbor. That is,
E = (p(Xn, 2 rj.
Given a subset U, the (U, reseprruted events are the events E := E {X, UU.
Next, similar in spirit Lemma 20 of Dasgupta and So (2024), we bound how frequently r-separated events occur with respect to the packing number.
Lemma D.4 (Packing bound). Let (X, p) be metric space, U X be subset, 0, and (kn, )n be regular sequence (Definition 4). For any process X. the number of (U, (U)raarrdd events that occur before time N is bounded by the r-packing number of U,
Σ E occurs} S 22x
Proof. Let 1i,.... . The index all instances where the (U, -ssparrtd event E occurs. Construct graph with vertices r....... such that (n, n2) is a directed edge if and only if S ny and X,, was one of the (kn, -earest neighbors of Xny- See also Figure We make two claims:
1. Any independent set in this graph must form an r-packing of U.
2. The graph has an independent set of size t/2kN-
Together, these two claims imply the result, since it shows that t/2kN S PU,,,, recalling that is the total number of (U, rssepartdd events that occur by time N. We now prove the claims:
Claim 1, Let n; S ny. By construction, when (n,, n,) is not an edge, the points X,,, and X,, must be r-separated; this is because X,, can be no closer to Xny than the k,, th nearest neighbor of Xny- Thus, any independent
the graph must form an r-packing U.
Claim 2. The graph has total of most Ei=, (kn, 1) < t (kx 1) edges (ex is larger than kn, by the regularity of (k)) It follows that the average degree is at most 2(kx - 1). Applying Turan's theorem, the graph must have independent of size least:
t
2k
2kx
23

---

X
X
Definition D.9 (Tree structure: Definition 24 from Dasgupta and So (2024)). For the above sequence of cover trees and insertion ranks, we let 0₁ be the root of A. For all k 1, there is ball Bla,, 2 2--++) E Cę-1 containing ag. We assign such an a to be the parent of ag, and we say that Figure 2: We say that an r-separated event occurs when the th nearest neighbor of X,, is r-separated from X,, Thus, the ball ((.,. r) contains at most kn neighbors.
D.5 Properties of cover trees
Next, we review cover trees, which were introduced by (Beygelzimer al., 2006) and book-keepinn device applied by Dasgupta and So (2024). We begin with several definitions and lemmas taken directly from Dasgupta and So (2024). We refer the interested reader to view their work for intuition behind these ideas: for our purposes we will simply state them for completeness.
Definition D.5 (Dyadic cone: Definition 21 from Dasgupta and So (2024)). Let (X, p) have unit diameter and let X. A dyadic cone centered of rank Zzo is the discrete collection of balls:
cone(a; I.) = ( (B(x,2 2 2 and E Zzo)- When 2 T., we also refer cone(1; T.) within cone(a; T.) as its rank-T/ tail.
cover trees: Definition 22 from Dasgupta and So (2024)). Let (X. p) have unit diameter and A = ( be dataset in without duplicates. The cover trees (C&)& with insertion ranks (L*) are defined:
Definition D.6 (Sequentially-constreee
C1 cone(a1; L1),
L1 = 0,
Cx Cx-1 U cone(ag; Lk),
L min {e Zzo : no ball of radius 2 in Cx-1 contains x
We say that was inserted into the cover tree at the T.gth rank.
Definition D.7 (Cover-Trees Neighbor Map: Equation 7 from Dasgupta and So (2024)). We define a cover-tree neighbor map c X Aigk Ct as any satisfying:
cu (x) B(a,r)
E ((a, 2r) and r/2 < p(z, Acx) <r.
(12)
Dasgupta and So (2024) show that such maps always exist with the following lemma.
Lemma D.8 (Lemma 23 from Dasgupta and So (2024)). The cover tree fx.for Açg has a cover-tree neighbor map tg-
ag its child. A instances inserted the same rank the same parent is called a generation of children. The number of generations of children dg has at time n defines the upper triangular array (Gr.n)knn
Gk. LR a is the parent of ag where k' $ <n)|.
Lemma D.10 (Cover tree 8-tail: Lemma E. from Dasgupta and So (2024)). Let (X, p. v) be upper doubling metric space with unit diameter Let (Cx)& be chain of cover trees for the sequence
24

---

A = (ax) k and let (L be its sequence of insertion ranks. Define the array of tail ranks (Tkmn)ssn and tail sets (An)a.
Ig
+
Gk.n
and
An
U B(ak:22 k=1
where d is the doubling dimension and e is the upper doubling constant in Definition 3. For all the mass of the tail is bounded v(A.) <
For the final lemma in this section, will modify Lemma 25 from Dasgupta and So (2024) in order to apply for heeresst neighbors (rather than only 1-nearest neighbor).
Lemma D.11 (Cover tree decomposition). Let (X, p) have unit diameter, let X a process in X, and let I be indicator process. For any n, let C be cover tree for X [I<n] with cover-tree neighbor map t. Assume that Xn & X[Ien] is not equal to one of the indicated instances. Then:
(aX, E
(x()) A.D..
x(kkm)
[X[Tea]]] c
U B(a.r)EC
(F% = and c( (Xa) = B(a,r)},
where E (Definition D.3) denotes the event that Xn has distance least r. from kn-th nearest neighbor in Ken. In particular, the event within the union indexed by B = B(a,r) E C is contained E2Brr/2
Proof.
Let Let c(x,) = B(a,r) r) for some > O. Suppose that X,, indeed has some nearest neighbor that located within the indicated instances. By the definition of a cover tree neighbor, there must exist
some X, E [[]] such that p(Xn, X,) 2 z This implies that the -earest neighbor distance of
X₂ is at least r/2 which implies / does indeed occur. Finally, the fact that Xn. E (B r) is immediate from the definition of a cover tree neighbor.
25

---

E Tie-breaking details
In this section, we formalize the tie-breaking strategy and show that the techniques introduced earlier also apply. Let (X1, .i...., .NN, , YN) be an adaptively sampled dataset. For a new query point E N. we sort the dataset X(1,, XM( by the lexicographic ordering on the pair:
Thus, the ordering is foremost determined by the distance of an instance I, so that p(z, ((m) is monotonically increasing with n. And if there are distance ties with p(æ, x(m)) = p(x, x(n+1)), then the instance that entered the dataset earlier takes precedence. The kn -earest neighbor query consists of taking the first kn indices under this ordering.
turns out that we can describe the k,, neighbor query as a relatively simple composition of spatial queries (Definition 8). In addition to the ball queries (Definition 11) defined earlier, need
the shell queries, which are spatial queries over sets of the form S, = {= E X p(x, 2) = r). Then,
the k, -nearstt neighbor query (with tie-breaking) can be given as follows:
Definition E.1 -nerest neighbor query). Fix x E X and & [N]. Let (X1, Y,, ,N,,,,NNNN YNn) be an adaptively sampled dataset. Then:
Let B =B, r>> 0} be the set of open balls centered x where B, B(x,r).
Let S. (St : 0) be the set of shells centered at x, where S, r)),r) \ B(r,r).
The k-nearest neighbor query is the adaptive query:
QNa(x)= = NN (B.) U (N,)(S,)
where r arg max {1QN,A (B(x, s))l 2 kk.
s>0
and where { = 1NN, Thus, QN. selects for exactly is points by finding the smallest closed ball containing at least k points, selecting for all points in its interior, and filling the remaining quota from the boundary, taken in order of arrival.
E.1 Sandwich numbers and concentration
Notice that any uniform concentration for spatial queries over closed balls directly carries over to spatial queries over open balls: for every open ball B, E B3 and dataset (X,,Y1.... Y1,..,,NN YN), as long as 8 < r is sufficiently close to r, then the queries coincide N, (B,) = (N,c(B.).
We need to provide uniform concentration of the class of spherical queries ( A very similar proof to Lemma 13 yields the following bound on the sandwich number of Sy:
Lemma E.2 (Sandwich number for spheres centered at x)) Let (X, p. v) be separable metric space with a Borel probability measure. Fix x E X and let S, be the set of shells centered at æ. Then, for any a E [0, 1), the a-sandwich number NB. (ai) of S₂ most 4/a.
Proof. Let X and let F(r) be the cumulative distribution function of p(x, Let M e N be any number greater than or equal to 1/a. For m = O.....
....... M, define:
mm min (r 2 0: F(r) 2 m m/M),
where I'm exists because is upper semi-continuous and is possibly infinite. We claim that the following collection of rings and shells forms a-sandwiching cover of S.,
M C U (Biz,rm) rm) B(x, rm- S(x,
from which the result follows by letting M = [ since 4/a 2 2- +1 (C). We now choose Am Aout C satisfying the a-sandwiching condition for any S(x,r) E S.. Let m E (O....,M) be the smallest number such that F(r) < F(r.)) There are two cases:
(a) If Tm, then we let An Aout S(z, rm). The sandwiching condition evidently holds.
26

---

(b) r < Tm, then we let An = 2 and Aout B(x,Tri \ B(x, rm-1). By construction of rm. v (1, s)) < m/M,
88 < Ti-
By the continuity of measure, we obtain v (B rmm) S Sm/M By construction of fm-11 U(B(I, 1)) 2 (m-1)/M.
It follows that (Aout)) S 1/M aa
Lemma E.3 (Concentration for the k-nearest neighbor query). Let (X1,Y2.... adaptively sampled by an -unfformyyyy dominated process. Let v be independently sampled. Let X(). ,..., (MM) the instances by ascending lexicographic ordering on the pair:
be
(p(2,Xi4 n.),
Let 1, E (0, 1). Suppose that 2
500 p
1 + log ki + log 1. + log
Then:
(I/NN
k Σ j=1
Pr
v()
2 Sp.
h:
Proof. Since Z is chosen independently from the data and let A B2 US consist of the open balls and shells around Z. Thus, as shown in Definition E. the k-nearest neighbor query centered at Z is the union of two disjoint queries:
Q1,22 U (A)
ME(M]
The result follows by proving uniform convergence over queries that are the disjoint union of two such queries. As Z is independently chosen from the data, we may apply the uniform convergence result Lemma 14. In particular, by a union bound, with probability at least
28 QQI
12 Na(a)
AQ E U (A), mE(M)
(Qx(Q) - (N( S
+ V
log
2([ E)
where we let = and f = 2 log 2N(( + + P
Let Q1 and Q2 be two disjoint queries satisfying the above incquality. Let QIuQ2 and |Q| k. Without loss of generality, assume IQ1l 2 k/2. Then, we claim that:
28 [Qil
Na(()
iN (Q) 7N (Q) <
2(1 E) log
(13)
where the light-hand side of Equation 13 is less than when is is sufficiently large:
168 + 8 logk
k
t
In particular, this holds when Q is k-nearest neighbor query.
Lemma 13 and Lemma E.2 bounds (a) s 8/o. So indeed, is sufficiently large:
168 + 8 8log k
32
log 2 + e² log k + log 8 a p
+log
500
1 + log k + log =-((1/) + log 1
1
k,
f2
p
since log ++++ e² +log& 8 < 12.
Proof of claim. Let C = V log
There are two cases:
8
27

---

1. Case 1: [Q2l > 2C.
1
-()())
-
(1Q1l ( AN( + 1Q2l (nv(Q2) -NN (Q2)
[
1
1011
12
-
48 CV
CV
1Q11 - + +C
Q1
[Q2l -
1011
48 + 2C
Q11
1Q11 -
28
h: (a)
= 2
1Q1l
V 21 -
log
p
2. Case 2: 1Q2l S 28.
1
(Qx(Q) - -x(())
5 (Q1))) 7N + 1Q2l
ÍNN (Q2) .N (Q2)
Q
1
1Q 2
k Na)
4e
log
Q
2(1Q1 -
p
(a)
2
+
log
|Q11
2((211 -
p
Proof of Theorem 2. Recall that Theorem 15 proved consistency for the k2 -nerestt neighbor rulc when 17 continuous, under the assumption that almost surely distance ties occur. That assumption only came in so that the concentration bound for k, -ncaest neighbor queries without ties, Corollary 2, could by applied. By replacing that with the concentration bound for k, nnarest neighbor queries with tie tie-breaking, Lemma E.3, we immediately the result.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: this is theory paper. the intro/abstract describes results which are proved in the body.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We describre the full scope of our theorems rigorously.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

well theorems are proved and correct to the best of our knowledge. The statements are rigorous (meaning assumptions are included).
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
30

---

Answer: [NA]
Justification: No experiments
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/ for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips. pttips.cc/puui cc/publi copublicgguii /eoidddee/eeeeuiieie wwriissssoooooogoooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: no experiments Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: no experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
31

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: no experiments
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp///eerrpp//eeee//eee//e httpppccc/ppttttttttttttuuu lines?
Answer: [Yes]
Justification: yes, we made sure it conforms to ethics. This is a theory paper about nearest neighbors.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: this a theory paper discussing online nearest neighbors. The introduction outlines the significance of our results which clearly does not have any negative societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
theory paper
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: cited everything, and this is theory paper code used.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswe thcode. com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: theory paper
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: theory paper. no human subjects or crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: no study participants.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
34

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: no LLMs used.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer our LLM policy (https: (https://neurips. //t////rr...ccc/ooffeeeee/////// for what should or should not be described.
35


Reviews:
[{"review_id": "jOuMXbxTP4", "reviewer": "Reviewer_hNva", "summary": "This paper studies the consistency of $k_n$-nn classifiers under noise & adaptive (non-iid) data generation processes in general metric spaces. This continues a line of work on the consistency of the $k_n$-classifier under more challenging settings and belongs to the broader scope of online learning in between worst-case adversarial and iid . In particular this paper extends the results of Dasgupta and So (NeurIPS 2024) from 1-NN to general $k_n$-nn and from noiseless to benign noise. They have two main results:  $k_n$ is consistent (for specific choices of $(k_n)_n$) under a distributional assumption related to absolutely continuity if additionally\n\n1.  and the Bayes optimal classifier is continuous, or\n2. the metric space satisfies a certain doubling dimension based assumption.\n\nThey also discuss that under weaker assumptions consistency typically fails.", "questions": "Consider adding some corollaries for common settings (Euclidean etc.).\n\nYour assumption on $k_n$ in Equation (2) requires knowledge of $\\varepsilon$. It is of course not really realistic to know $\\varepsilon$. Is there some way to make it work without knowing $\\varepsilon$? E.g., guess it by some doubling trick etc.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper studies an interesting and challenging problem. It greatly extends the work by Dasgupta and So (2024) on consistency results for 1-nn to $k_n$-nn. It fits nicely into the recent line of work on online learnability between adversarial/worst-case and iid (i.e., learning under general adaptive stochastic processes). \n\nThe structure of the paper is not ideal. On first sight the purpose of sections 2-5 is not very clear. Section 2 and 3 provide some more intuition on the challenges in this setting, Section 4 and 5 give a proof overview on the two main results. Perhaps try to clarify this.\n\nAlso the discussion of related work is rather limited. Please discuss more exactly how you relate to similar settings (e.g., Hanneke et al., 2021). In particular please discuss how your assumption relate to previous assumptions in other works (as you did for Haghtalab et al., saying you generalize it).", "was_revised": true, "final_justification": "Good paper and important problem.", "rebuttal": "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:\n\n**Relationship to prior work.**\n\n\nOne 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). \n\nThe 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.\n\nThe 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). \n\nHowever, 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.\n\nThus, 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.\n\n**Response to question.** \n\nOn 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).\n\nFor 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."}, {"review_id": "NoiukdwsCf", "reviewer": "Reviewer_1qFD", "summary": "The paper considers the problem of asymptotically proper prediction of binary labels for online (adversarial) sampling from a given space. The authors provide a complex mathematical analysis of the algorithm based on $k_n$-Nearest Neighbor, for certain parameters $k_n$ depending on the sampling round n and for data generation process that, although allowing adversarial actions, it guarantees that intractable worst-cases generation patterns occur with negligible probability. Additionally, the authors claim that their analysis includes the presence of noise.", "questions": "1.\tCompare results with previous work, focusing on differences.\n2.\tDefine noise formally.\n3.\tEmphasize novel techniques and their impact in the analysis.\n4.\tHow to obtain proofs of Theorems 2 and 5 from technical lemmas?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Pros:\n\n-\tThe problem itself is among fundamental theoretical ML problems\n\n-\tMathematical analysis is quite complex\n\nCons:\n\n-\tThe novelty of the analyzed setting is unclear, comparing to the previous work. It looks like the main difference is noise, but I couldn’t find its formal definition and use in technical parts. I also couldn’t find a satisfactory comparison with the previous work(s)\n\n-\tThe result holds under certain assumptions, including Borel measurable spaces, continuous label distribution function (or measurable function in upper doubling space), etc. \n\n-\tThe authors assume that the reader is fluent in various aspects of mathematical statistics and topology\n\nDetail comments:\n\nThe title does not say anything about the actual angles of the paper – the problem, adversarial setting, noise, etc.\n\nThe concept of noise is not formally defined in the main paper, only by the means of examples. It is not clear what are real difference in the setting and techniques between this work and Dasgupta and So, NeurIPS 2024. The authors are not clear in referencing results to previous work, especially results stated without any proof. \n\nThe proof of the main Theorem 5 is somehow stopped and hand-waved closer to the end. I could follow the analysis (up to some presented level of details) up to Lemma 17, but Section 5 is far too sketchy.", "was_revised": true, "final_justification": "The rebuttal helped me to understand better the significance of the presented results vs previous work, which is above acceptance bar. However, I still do not see substantial technical novelty, which seem to me a kind of \"randomized relaxation\" (this is what I meant by Yao principle - the process gets more randomness, and Yao principle connects random executions with worst case deterministic ones) of the analysis in the previous work(s). I may be wrong in it, but the authors did not convince me otherwise with their too general arguments. I keep my borderline reject score; however I do not oppose acceptance if other reviewers are convinced that the paper is above NeurIPS acceptance bar.", "rebuttal": "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:\n\n**Relationship to prior work.**\n\nOne 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). \n\nThe 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.\n\nThe 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). \n\nHowever, 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.\n\nThus, 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.\n\n**Clarification on noise.** \n\nDasgupta 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}$.\n\nPerhaps surprisingly, the existence of label noise introduces a lot of new challenges to analysis (see Sections 2 and 3), which we discuss next.\n\n**New techniques and impact.**\n\nTo 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.\n\nHowever, 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.\n\nThere 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).\n\n**Improved proof sketches.**\n\nThank 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\n\n1. 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). \n\n2. 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.\n\n3. 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.\n\n4. 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."}, {"review_id": "qnZBP6vpAb", "reviewer": "Reviewer_ZWJH", "summary": "This paper studies the consistency of the k_n-nearest neighbor rule under an adaptive adversary and label noise. They show that the k_n-nearest neighbor rule is not conistent under such an adaptive adverasary. The authors complement this negative result by showing that one can recover consistency by placing additional mild assumptions on the adversary.", "questions": "- See Weakness above for questions regarding organization\n- What are some examples of upper doubling spaces?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n - I think the results of the paper are interesting and provide a clear contribution to the existing literature on the consistency of k_n-nearest neighbors. \n- Moreover, I think this paper contributes nicely to the growing literature on beyond-worse-case analysis \n- Finally, I thought the Theorem statements were surprisingly clean and easy to parse.\n\nWeaknesses: My main gripe with this paper is its organization. While the authors do a nice job of summarizing the main results in Section 1.2, it was not immediately clear how the remaining sections map to these main results. Moreover, I often got lost reading through some of the (often verbose) prose wondering what the main point is and how it connects to the main contributions stated in Section 1.2. For example, instead of providing a proof sketch of Proposition 7, the authors provide a \"false proof of convergence.\" What is the point of lines 133-137?  What is the point of Section 3 how is it used in the proof of the main claims in Section 1.2?  Definition 12, Lemma 13, and Lemma 14 are not about k_n-nearest neighbor. How do these connect to the main claims and what is the point of Section 3.1? In my opinion, a paper should be focused on substantiating its main claims, with sections clearly labeled indicating which claim is being addressed. This is not the case with this paper, which to me, reads as if it were written from a stream of consciousness (e.g. lines 138-142).", "was_revised": true, "final_justification": "I maintain my positive score as the authors have adequately answered my questions.", "rebuttal": "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.\n\n**Verbosity.** \n\nWe 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.\n\n**Connection between Section 3 and main results.** \n\nTo 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.\n\nHowever, 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)?\n\nThe 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.\n\n**Examples of upper doubling spaces.**\n\nThe 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."}, {"review_id": "UfZ7nGkYnr", "reviewer": "Reviewer_XUWz", "summary": "In this paper, the authors consider online binary classification under an adaptive sampling model (i.e., the sequence of prediction tasks can adapt to the sequence of observed labels). A KNN based procedure is proposed and is shown to be consistent (approach Bayes optimal performance) under the assumption of \"uniform absolute continuity\" of the data process (a type of smoothness condition) and appropriate choice of $k$. Under a stronger assumption of ``upper doubling\" on the metric space,  KNN is further shown to satisfy universal consistency for any measurable label function $\\eta$. It is also established that in the worst-case setting, the $k_n$-nearest neighbor rule can fail to be consistent.", "questions": "- I'm a bit confused about Line 106. Are the labels not supposed to be random?\n\n- The results seem to me very geometry-tied, which may be an artifact of the particular algorithm under consideration. Is there a sense in which kNN is the best thing to do here? The setup is very close to a bandit / online optimization setting,  where the type of guarantees / assumptions / optimal algorithms are quite different from the proposal here.", "limitations": "Yes it's adequately addressed.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Overall, the results presented in the paper constitute solid theoretical contributions, that is generalized from previous work on i.i.d to the sequential and noisy label setting. The claims are sound as far as I can tell, and the paper is well-written with clear presentation. The problem itself is also of great interest to the ML community at large.\n\n\nMy main concern about this paper is its practicality. The distance calculation upon seeing every new observation, and the memory requirement for such a KNN-based algorithm is not scalable to high dimension and/or large data. In another direction: how robust is the choice of $k$ here, since the smoothness parameter $\\epsilon$ is almost impossible to know exactly. I also don't think conditions like upper doubling is easy to check in practice.\n\nThe paper can use some reorganization: the related work section should come earlier with a conclusion in the end. I find some parts a bit technical and better pushed to the appendix with sketches of the argument in the main text sufficient.", "was_revised": true, "final_justification": "I believe the paper has made contributions to the problem under study and has extended previous results to new settings, although it will benefit from improvements on the presentation.", "rebuttal": "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.\n\nTo address the remaining questions:\n\n**Practical considerations.** \n\nIt 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.\n\nIn 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.\n\nA 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.\n\n**Choice of $k_n$.**\n\nThe 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)$. \n\n**Upper doubling condition.**\n\nAn example of an upper doubling space is Euclidean space with the standard Lebesgue measure.\n\n**Confusion about Example 6.** \n\nThis 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).\n\n**Geometric nature of analysis.**\n\nThe 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.\n\n\nBeygelzimer, Alina, Sham Kakade, and John Langford. \"Cover trees for nearest neighbor.\" Proceedings of the 23rd international conference on Machine learning. 2006.\n\nIndyk, Piotr, et al. \"Locality-preserving hashing in multidimensional spaces.\" Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. 1997.\n\nKusner, Matt, et al. \"Stochastic neighbor compression.\" International conference on machine learning. PMLR, 2014.\n\nGelman, 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."}]

Author rebuttal:

Meta-review: Summary  
This paper considers the adaptive sampling model of online learning, specifically, the k-nearest neighbor learner. Under mild assumption that the process generating the instances is uniformly absolutely continuous and that the underlying conditional label distribution is continuous, this paper shows that k-nearest neighbor rule is consistent.

Strengths  
- This paper studies an interesting and challenging problem, greatly extending Dasgupta and So (2024) on consistency results for 1-nn to k_n-nn.
- This paper conteibutes nicely to the growing literature on beyond-worse-case analysis.
- The problem studied is a fundamental theoretical problem.

Weaknesses  
- Multiple reviewers mentioned that the structure of the paper could be improved to be more easily readable.
- The discussion of related work could be improved.
- Reviewer XUWz concerned the memory requirement for this KNN algorithm might limit the scalability, and the robustness of the choice of k.
Decision: Accept (poster)