Online Consistency of the Nearest Neighbor Rule
Authors: Geelon So
Sanjoy Dasgupta
Venue: NeurIPS 2024 poster (2024)
Keywords: Nearest Neighbor Classification
Online Learning
Smoothed Analysis
Primary area: learning_theory
TL;DR: The nearest neighbor rule is online consistent under much broader conditions than previously known.

Abstract: In the realizable online setting, a learner is tasked with making predictions for a stream of instances, where the correct answer is revealed after each prediction. A learning rule is online consistent if its mistake rate eventually vanishes. The nearest neighbor rule is fundamental prediction strategy, but it is only known to be consistent under strong statistical or geometric assumptions: the instances come i.i.d. or the label classes are well-separated. We prove online consistency for all measurable functions in doubling metric spaces under the mild assumption that instances are generated by a process that is uniformly absolutely continuous with respect to an underlying finite, upper doubling measure.

Online Consistency of the Nearest Neighbor Rule
Sanjoy Dasgupta
Geelon So Department Computer Science UC San Diego La Jolla, CA 92023 geelonêucsd. edu
Department of Computer Science
UC San Diego
La Jolla, CA 92023 dasgupta@ucsd. edu
Abstract
the realizable online setting, a learner is tasked with making predictions for a stream of instances, where the correct answer is revealed after each prediction. A learning rule is online consistent its mistake rate eventually vanishes. The nearest neighbor rule (Fix and Hodges, 1951) is fundamental prediction strat- egy, but is only known to be consistent under strong statistical or geometric assumptions- instances come i.i.d. or the label classes well-separated. We prove online consistency for all measurable functions in doubling metric spaces under the mild assumption that the instances uniformly absolutely continuous with respect to finite, upper doubling measure.
generated by process that is
Introduction
In online classification, a learner faces a never-ending stream of prediction tasks. For all times n:
the learner is presented with an instance X,,
the learner makes a prediction Y,,
the ground-truth label Yn is revealed.
When the instances come from some underlying metric space, one the simplest prediction rules the leamerr can employ is the nearest neighbor rule (Fix and Hodges, 1951). This learner memorizes everything it sees, and when it comes time to make a prediction for a new instance X,, it looks for the most similar data point in memory, predicting with that nearest neighbor's label. In this work, we are interested simple conditions under which the nearest neighbor rule is fact a reasonable strategy, where the rate at which the learner makes mistakes eventually vanishes.
Let (X, P. v) be a metric measure space where p a separable metric and is finite Borel measure. We study the realizable setting, in which the ground-truth labels Y, n(X,,, are given by some measurable label function n X + y. Let X = (X,).20 be any stochastic process. induces nearest neighbor process X (X) 18)n0 which is any process satisfying:
Xn arg min x)),, xEXc.
The nearest neighbor rule predicts using the label V, = (xx)), and it is online consistent when the asymptotic mistake rate the problem instance (X, 11) goes
N
lim sup
1
Σ (x( 1=1
+ (x =
a.s.
(1)
N
N
There are two representative results for the online consistency of the 1-nearest neighbor rule in this setting-bon both impose strong constraints on either X 1). Cover and Hart (1967) assume the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Algorithm The 1-nearest neighbor rule
1: for n mt=11 =: 1,,,, 2,... do
2: Receive the instance X,,
3: Predict with nearest neighbor label my(Xx,)
4: Observe and memorize the ground-truth label (7())))
5: end for
statistical constraint that is an i..dd process. In contrast, Kulkarni and Posner (1995) allow for arbitrary processes. However, they assume the geometric constraint that points of different classes ((x)) & nTz') are uniformly separated p(z, x') > e > 0 in totally bounded space.
The result of Kulkarni and Posner (1995) turns out to be tight in the absence of further assumptions. As long as there are points belonging to different classes that are arbitrarily close together, then there are udversarial sequences which the nearest neighbor rule is not online consistent (Proposition 2). Still, this negative result does not necessarily spell doom for the nearest neighbor rule in all non-i.i.d settings; one of our aims is to understand just how pathological these worst-case sequences are.
The upshot of this work that worst-case sequences on which the nearest neighbor rule fails to learn are in fact extremely under quite mild constraints on X and 17, they almost never occur. The nearest neighbor rule online consistent under much broader conditions than previously known.
1.1 Main results
Consistency for functions with negligible boundary We first consider learning label functions with negligible boundary, where almost every point has positive separation from other classes. As the separation may be instance-dependent, this relaxes the uniform separation condition of Kulkarni and Posner (1995), and it is equivalent to the assumption used by Cover and Hart (1967).
It turns out that if the label function has negligible boundary, we can cover essentially all of X with mutuall--lbbeling balls (Definition 8). On such a ball, the nearest neighbor rule makes most one mistake (Lemma 9). So, progress is monotonic: eventually, all mistakes must come from a remainder region with arbitrarily small y-mass (roughly, points arbitrarily close to the decision boundary).
follows that if we can limit the rate at which X comes from regions with arbitrarily small mass, can also limit the mistake rate of the nearest neighbor rule. To this end, formalize the notion of an ergodically dominated process (Definition 3), which is a process where the asymptotic rate function of v v(A). In particular, these processes do not
of landing in region A is bounded hit regions with arbitrarily small mass at a constant rate. With little ado, we can show that the nearest neighbor rule is consistent when ergodically dominated and n has negligible boundary (Theorem 7). Stronger, quantitative assumptions also yield rates of convergence (Theorem F.2).
Universal consistency This first consistency result for functions with negligible boundaries is quite general and captures many settings of interest (e.g. classification on IR with smooth decision boundaries). But not all functions have s-negligible boundaries, we also study when the nearest neighbor rule is universally consistent (i.e. consistent for any measurable 77). This question is trickier since boundary points, which are hard for our learner, need not be localized to set of measure zero.
We proceed by giving more structure to (X, p, v) and X. First, we let p be a dd-oubling metric (Definition 11). This is helpful because every measurable function 1/ can then be approximated arbitrarily well by a function '/' with negligible boundary (Proposition 13). And so, it seems that might be able to deduce universal consistency of the nearest neighbor rule almost directly from the previous result- learning is perhaps not so different from learning 7/ when their disagreement region is made to be vanishingly small. However, this turns out not to be the case.
For example, Blanchard (2022) constructs classification problem where the nearest neighbor rule is not consistent, but X' is 1-doubling space (the unit interval [0. 1] with the usual metric), is measurable, and X is ergodically dominated. The problem is that, even the disagreement region is made to be extremely small, its influence on nearest neighbor predictions is not limited to the times when instances land in These instances exert influence when they themselves are nearest neighbors of downstream instances. In other words, 'bad points' can accumulate in the memory of

---

the nearest neighbor learner, and their influence grow and shrink with their Voronoi cells (regions where they are nearest neighbors). As the region on which the nearest neighbor learner is prone to make mistakes waxes and wanes throughout time, we cannot argue that progress is monotonic in the same way as before. In short, a tail constraint on X is no longer sufficient for consistency.
To show universal consistency, we constrain X at every moment in time. Ergodic domination only ensured that the time-averaged rate which X hits small regions small. We now require the time- uniform rate to also be small, a strictly stronger condition. Formally, uniformly dominated process (Definition 4) is one where the probability that the instance X,, lands in region a function of v(A) at each point in time. Intuitively, ergodic domination is retrospective: looking back, how often do points land A? In contrast, uniform domination is generative constraint: at any point in time, how easily can the underlying mechanism generating X select a point in A?
bounded as
The basic argument then is that even though 'bad points' doubling space, their Voronoi cells also tend to shrink quickly when they are hit by further instances. If the mass of these Voronoi cells were to shrink as well, then it would become increasingly unlikely that these instances are nearest neighbors of downstream points whenever X is uniformly dominated. So that having small metric entropy implies having small mass, we let the measure be upper doubling (Definition 11, by which we mean that the mass of a ball of radius r is bounded by (
accumulate in space over time, in
We first prove the following result, which may be of interest in its nearest neighbor processes: when X is a uniformly dominated process in an upper doubling space, any nearest neighbor process X is ergodically dominated (Theorem 14). Simply put, this means that two functions/ and ny' rarely disagree, then the average rate at which nearest neighbor processes land in their disagreement region is also bounded. Universal consistency now follows fairly easily.
right, about the behavior of
Let 1) be closely approximated by some n/' with negligible boundary. The asymptotic mistake rate of the nearest neighbor rule on n/ is zero when X is uniformly dominated. On the other hand, if the mistake rate on v7 is large, this discrepancy must be due to the influence of their (very small) disagreement region. But, large discrepancy is not possible as the nearest neighbor process is unable to significantly amplify the influence of very small regions. Thus, the nearest neighbor rule is universally consistent upper doubling spaces for uniformly dominated processes (Theorem 12).
Notation Given a sequence X. we let Xen denote the set (X...... Xn- The symbol 1 denotes the indicator function, which is equal to I when the event that follows occurs and 0 otherwise. We let B(x,r) C X' denote the open ball of radius r centered at x. For any E X and Z c X, let:
p(x, Z) = inf p(xx2) sEZ
and
diam (2) = sup 2(2,2').
2.2'22
2 Non-convergence for worst-case sequences
To motivate the study of worst case sequences, let's 's first consider a worst- example showing that the nearest neighbor rule can make mistake in each round learning a threshold function:
Example 1 (Failing to learn a threshold). Let X' = [-11, 1] and let n=0) f 2 0} be a threshold function. Let X be defined by Xn = (-1/3)". The nearest neighbor rule makes a mistake every round n + 1: the nearest neighbor of X 1 Xn, which has the opposite sign (see Figure 1).
More generally, the hardness of point for the nearest neighbor rule depends on its separation from points of different taases-harte sequences exist precisely whenever the classes are not separated:
Proposition 2 (Non-convergence the worst-case). Let (X, p) be totally bounded metric space. Given 7 X + y, there is a sequence of instances (X,)n which the nearest neighbor rule is not online consistent on 17 if and only if there is no positive separation between classes:
inf ((()=
p(x,x') =0
While the nearest neighbor rule can fail to learn many functions of interest, in both the example and the proof of the proposition, the mode of failure depended on the ability of worst-case adversary to select instances with arbitrary precision. This can be seen the threshold example, where the interval on which the leamner can make a mistake shrinks exponentially quickly.
3

---

X1
X3
X2
Figure 1: Learning the threshold {a 2 0} on R. The nearest neighbor classifier makes a mistake every single round on the sequence X, = (-1/3)", where subsequent test points alternate sign.
However, this mode of failure may not always be present, especially when the ability of the adversary select instances from small regions of space diminishes with the sizes of those regions. This may be the case if the adversary is limited in computation, information, or ill-will toward the learner. The question remains: what is the behavior of the nearest neighbor rule in such non-worst-case settings?
3 Two general classes of non-worst case sequences
To study this, let's formalize the generating process. At each time step conditioned on the past outcomes X<n. an adaptive adversary constructs distribution over X' from which X, drawn. In this way, any particular choice of adaptive adversary corresponds to a stochastic process, which defines probability measure over the space of all sequences of instances. We are interested in the almost-sure online consistency of the nearest neighbor rule under these measures.
In the standard ii.d. setting, each X,, is drawn from the same underlying distribution. In the worst- case setting, the conditional distribution of X,. X<n may be point masses and so X may be an arbitrary sequence. We introduce two mildly-constrained classes of non-worst-case processes. Both are given with respect to an underlying reference measure (which we assumed to be finite).
Ergodically dominated processes The first be considered class of budgeted adversaries. For any region A C X' the asymptotic rate at which the adversary can select points in bounded by function E( of (AA). In particular, ergodically dominated process do not concentrate in regions with small mass in retrospect.
require c(ō) > 0 as 8 goes zero. Instances from
Definition 3 (Ergodic continuity). A stochastic process ergodically dominated by if for any E 0, there exists d > such that when a measurable set A C X satisfies v(A) 5, then:
N
lumsup N
Σ 1(x,
EA <E
a.s.
(2)
N
n=1
We say that X is ergodically continuous with respect at e())
As pointed out by Hanneke (2021), the set function A - lim sop E E A} a submeasure. Then, ergodic continuity requires it to be absolutely continuous with respect to v. These processes are closely related the -popccssse introduced by Hanneke (2021). There, the submeasures must be exhaustive, which Talagrand (2008) shows to be strictly weaker condition than absolute continuity. Hanneke (2021) also demonstrates that there are Ci-processes on the unit interval for which the nearest neighbor rule is not universally online consistent.
Uniformly dominated processes The following can thought of as a class of bounded precision adversaries. Each time step, the probability that the adversary selects an instance from region A is bounded by a function e of v(A). Thus, it provides a time-uniform condition:
Definition 4 (Uniform absolute continuity). A stochastic process X is uniformly dominated by if for any E > 0, there exists such that when a measurable set C X' satisfies v(A) < 5, then:
sup Pr (Xn E A %<n)
MEN
We say that X is uniformly absolutely continuous with respect to at rate =(8).

---

This class can be seen as strict generalization of the o-smoothed processes introduced by Haghtalab al. (2020), which satisfy the Lipschitz rate E(6) 6/a (Definition F.3). This stronger, quantitative condition allows us to give rates of convergence for smoothed processes in Appendix F.
Time-averaged behavior of uniformly dominated processes We now show that ergodic continu- ity is weaker condition than uniform absolute continuity. And intuitively, the former lets us prove consistency when the hard or atypical instances come from a small, fixed region of space. The latter will be needed when the hard regions of space evolve over time.
In the following, we can think of (An), as a sequence of hard regions (e.g. the region on which the learner can make mistakes). By the martingale law of large numbers, if the mass of these regions eventually remain small, then the average rate at which X lands in hard regions also becomes small:
Lemma 5. Let % be uniformly dominated by v at rate =(0). and let (Fn)n be its natural filraation. Let An be an Fn Fa-predictable sequence where lim n ((An) < almost surely. Then:
lim N-000
L(x An S =(6)
a.s.
Setting A,, to A shows that ergodic continuity is weaker than uniform absolute continuity. In fact, as it only constrains the tail of X, it is strictly weaker (the ergodically- -ominnted adversary is stronger).
4 Consistency for functions with negligible boundaries
The inductive bias built into the nearest neighbor rule is that most points are surrounded by other points of the same class (though one might have to zoom in very close to the point). We first consider label functions for which this inductive bias is correct v-almost everywhere. Ergodic continuity with respect to shall be enough for online consistency. To formalize these functions, define:
Definition 6 (Boundary point). Let 1) X + Y be measurable. Let margin,, be the distance from x to points of other classes, and let 0 denote the boundary 1,, points with no margin:
margin, (x)
inf m())((()))
p(x,2x))
and
02p {xx X' margin, (x) = 0}.
Let Fo {u measurable: : x) = =} denote the set of functions with negligible boundaries.
The class Fo captures many label functions of interest. For example, when X' is Euclidean space equipped with the Lebesgue measure, then label functions with smooth decision boundaries have negligible boundaries-the boundary forms lower-dimensional manifold with zero measure.
Theorem 7 (Online consistency for Fo). Let (X, be metric measure space, where is separable metric and v is a finite Borel measure. Let X. be ergodically dominated by v and let have v-negligible boundary. The nearest neighbor rule is online consistent with respect to (X,, 11).
To prove this, we introduce the notion of mutually-labeling set, which are subsets U of X' that share single label under 7), and whose diameter is less than the distance to reach different class:
Definition 8 (Mutually-labeling set). A set U X' is mutually-labeling for if for all U,
diam (U) margin,, (z))
(4)
See Figure 2 for a picture. This construct is useful because the nearest neighbor rule makes at most one mistake per mutually-labeling set-see Lemma 9, Moreover, it is easy construct such sets; Lemma 10 shows that sufficiently small balls centered at non- non-boundary points are mutually- Lemma 9, Let U be a mutually-Labeling set for n. Let % be an arbitrary process. Then:
o
1 (xx, E and m((x)) + ((xn)) S
Lemma 10. For any 0 <r margin, (x)/3, the ball B(x, r) is mutually-labelie for n
5

---

Proof of Theorem 7. Fix E > O. We first prove that the asymptotic mistake rate is bounded by e. Choose 5 > such that the ergodic domination condition, Equation (2), holds. We claim that we can cover all of X by finite number K3 < oc of mutually- sets, except for region As of 6. By Lemma 9, at most one mistake can be made on each of the mutually- labeling set, so that all but finitely many mistakes come from Ag. Thus, the asymptotic mistake rate is bounded by the rate at which X can hit Ag. By definition of ergodic continuity, this is less than s,
small mass v v(As)
N E1{x E As} <E N
sup sup 00 N
Σ 1(((x,) + ((x)) & lim sup N
a.s.
n=1
==1
Online consistency follows by applying this simultaneously to a countable sequence of & O.O.
To finish the proof, we construct the above collection of mutually-labeling sets. By Lemma 10, we can cover almost all of X by the collection of mutually-Labeling balls, since we only miss out on the boundary points, which is v-negligible. This collection has countable subcover C = {Bi B2....} because is separable. By the finiteness of and the continuity of measures, when Ks is sufficiently large, the first K2 balls cover everything but region Ag of mass v(As) < 6,
As = X'
U BN. ASKA
A picture is also given in Figure 2.
5 Universal consistency on upper doubling spaces
We now show that the nearest neighbor rule is universally online consistent (that is, consistent for any measurable function) whenever X is uniformly dominated and X' is an upper doubling space:
Definition 11 (Upper doubling). A metric space (X, p) is doubling with doubling dimension d if every ball (zz, r) can be covered by 2d balls of radii r/2. A d-doubling space with measure is upper doubling if there exists e > 0 such that for all (xx, r), we have 1/ (B(zz r)) S crd.
This notion was introduced under a somewhat more general form by Hytönen (2010), and it relaxes the condition of a doubling measure space. For example, IRd with the disttnne and Lebesgue measure is readily seen be upper doubling with doubling dimension d.
Theorem 12 (Universal consistency). Let (X, v) be an upper doubling metric measure space, where p is separable metric and v is a finite Borel measure. Let X be uniformly dominated by v. For any measurable y), the nearest neighbor rule is online consistent with respect (X.1).
The doubling metric condition is helpful because the set Fo of functions with negligible boundaries then dense in L' (X:; v/), as shown in Proposition 13. That is, any measurable 1) can be arbitrarily well-approximated by Fu, for which we know the nearest neighbor rule is consistent.
Proposition 13 (Fu is dense in L'). Let (X, p. v) be a metric measure spaces where p is doubling and v is a finite Borel measure. Then, the set Fo dense in L' (X.v).
To show universal consistency, is not enough that can be well-approximatee by function v/o with negligible boundary. We also need know that their disagreement region {n A 1o0 cannot have excessive influence on the behavior of nearest neighbor predictions. The upper doubling condition allows us to show that when X is uniformly dominated, then X is ergodically dominated. We will use this to limit the rate that nearest neighbors come from regions where 17 is poorly approximated.
Theorem 14 (Ergodic continuity of nearest neighbor processes). Let (X, v) be a upper doubling space with bounded diameter. Suppose that a process X is uniformly dominated by There exists constants C1, C2 > O such that for any measurable set A C X with (AA) < do.
rate e(0).
N
E(6u) + =(0) a.s. log (at
lim sup N
Σ 188 E A] < inf 850
N
n=1
If we not optimize the bound and just let 5 = 60, this shows that when X is uniformly dominated at rate E()), then X is ergodically dominated at slower rate OEE()) log J). We can now show:

---

Proof of Theorem 12. E > O. Let X be uniformly dominated and let 17 be measurable. We prove that the asymptotic mistake rate of the nearest neighbor rule for (x, is bounded by 32 almost surely. The result follows by simultaneously applying this to a sequence E; + O.
Let 1/0 Fo be do-accurate approximation of 1) so that (11 no)) < do- We will set dg later. If at time n, the nearest neighbor rule makes a mistake, then at least one of three events must occur:
(a) The functions 1) and Too disagree X
(Xx)
mistake
n(Xn)
(b) The functions and no disagree on Xn,
(n)
(b)
(c) The nearest neighbor rule errs at time n on (X,
77 (X,)
(0)
7/0
(oo(Xx (X.)
Lemma 5 implies that (a) contributes at most E(6o) the asymptotic mistake rate, while Theorem implies that (c) contributes nothing. We just need to bound the contribution of (b) for when the nearest neighbor process lands in the disagreement region of r and rj-- For this, we can almost directly apply Theorem 14, except that it assumes that the process takes place in a bounded space.
It turns that because is doubling and is finite, there is bounded region X X that captures the vast majority of and X; Lemma D.4 bounds the rate at which either process escapes N,,
N Σ
(d) limsup N-+00 n=1
1(x, 2 or Xn $ Xz) <
a.s.
Having accounted for mistakes outside of Xg, we can consider the amended event (b') that r and no disagree on A = X₂ n {1 # no)- Since v(A) < da, we now apply Theorem 14; when ei and 0 are the corresponding constants given by for the space (Ke, p. v), suffices to set óg > so that:
22 log 1 =66) + +=(6) <E.
inf 850
Then, to the asymptotic mistake rate, the events in (a) contribute at most E(6n) < e, (b') contribute another e, (c) contribute nothing, and (d) contribute Together, they yield the target 35 bound. L
Ergodic continuity of nearest neighbor processes
The nearest neighbor rule does not forget; and so, data point X,, can be the nearest neighbor of an unbounded number of downstream instances Xyn. In this section, we ask a trickier question: at what rate can set of instances in X contain nearest neighbors of downstream points? More intuitively, how much influence can a set instances exert through the nearest neighbor process?
Theorem 14 gives one result of this form: informally, if process X can generate points from small regions only very rarely, then these points cannot make up significantly larger fraction of X. More generally, we consider the long-term influence of any asymptotically rate-limited subsequence of X. Formally, to indicate the instances whose long-term influence we wish to bound, we define:
Definition 15 (Indicator process). An indicator process (In),, is a sequence of {0, 1}-random variables. It induces a counter k(n) and the sequence of stopping times (Tk) where:
k(n)= 11
In and
min (n k(n) 2 k). Tk
That is, k(n)) is the number of indications given by time n, while 7 the time of the kth indication. We say that Il is asymptotically rate-limited by >> O if almost surely, lim sup, k(nz/ /n <
Notation 16 (Indicated instances). Let X be process and I be an indicator process. Let X [[]]] denote the subset of instances in X indicated by time n (not inclusive), so that:
X
[e]] {Xm m < n and Lm 1}.
(5)
For uniformly dominated processes in upper doubling spaces, if this set of instances doesn't grow too fast, then its aime-averaged influence is limited when filtered through the nearest neighbor process. For simplicity, in this section, will also assume that the space is bounded.
7

---

Theorem 17 (Long-term influence bound). Let p.V) be a bounded, upper doubling space. There are constants C₁2 C2 that the following holds. Let X be uniformly dominated at rate =(6) and let II be an indicator process adapted to X asymptotically rate- rate-limited by >> O. For any ō >> 0, the rate that the indicated instances X
x[T<* [Tc]] contain nearest neighhor Xn, is at most:
lim sup
Σ N-700
E <7 (a1
c2 log 8) + e(6)
a.s.
The ergodic continuity of X follows when we take I, to be 1 1[x, E A} and optimize the bound.
6.1 A metric bound for nearest neighbor events
To prove Theorem 17, we need balance two opposing dynamics. On one hand, more and more indicated instances fill the space as time goes on. On the other, the Voronoi cells of these instances- regions in which they are nearest neighbors- tend to shrink as they are hit. Mathematically. this can be seen by decomposing the event that an indicated instance is nearest neighbor like so:
Xx, E x [c]]
= U {x,, E Voronoi cell of x w.r.t. )
(6)
2EX[Len]
The natural proof strategy following this would be bound the probability that the left-hand side event occurs by arguing that the indicated Voronoi cells have small p-mass, so that these cells would be rarely hit if X is uniformly dominated. However, this decomposition does not seem be very fruitful as it is difficult to directly control how the mass of Voronoi cells evolve over time.
Instead, our proof strategy makes of both notions of size available Besides the measure of a set, recall the packing number of a set, a notion of metric entropy:
in metric measure spaces.
Definition 18 (Packing and packing number). Let r > 0. A set Z X' is an r-packing if all of its points are bounded away from each other by a distance T,
inf p(z, 2r. 2,
The r-packing number PU) of U is the maximum possible size of an r-packing Z contained in U.
The packing number bounds the number of times that the nearest neighbor distance p(X,., Xx.) is large. In particular, for any r > 0, the nearest neighbor distance can exceed r at most P,( times. This is because such set of instances must then form r-packing. As slight generalization: Definition 19 (r-separated event). Let be a process and r >> O. The r-separated event at time n is the event E, that X, is r-separated from all past instances X.n.
F = (p(Xn: Xn) 2 r].
Given a subset U, the r -separatd events are the events E := ET (Xn U..
Lemma 20 (Packing bound). Let (X, p) be a metric space, U C X be subset, and r > 0. For any process X. the number of (U, r) r--paraate events is bounded by the r-packing number of U,
Σ
1 (Fhir occurs) S PP(U).
Thus, we now have two ways of bounding how often an instance can appear in the nearest neighbor process: the number of times it can be distant nearest neighbor is bounded by the packing number, while the rate it can be a close nearest neighbor can be limited by the measure of small balls. The basic proof idea for Theorem 17 will be to slowly trade off the measure bound for the metric bound via an alternative decomposition of the event X₂, E X [ee]] based on the cover tree data structure.
6.2 The cover-tree decomposition
Definitions In this section, let A' be bounded metric space, which we may rescale to have unit diameter. Let us recall the cover tree data structure, introduced by (Beygelzimer et al., 2006), which is an efficient multi-scale ball cover for a given dataset: each data point is covered by a ball of every radius 2 for all E No N (0). First, we'll introduce the dyadic cone as multi-scale cover of single data point. Then, inductively construct the cover tree union of dyadic cones.
8

---

Definition 21 (Dyadic cone). Let (X', p) have unit diameter and let x: E X. A dyadic cone centered of rank Ng is the discrete collection of balls:
cone(1; L) = { (B(x; ) 82 : L and E No). When L' 2 L, we also refer to cone(2; L') within cone(a; L) as its rank-L' tail.
One possible way of constructing multi-scale covering of dataset is to take the union of all dyadic cones of rank zero centered all data points. However, this cover is not particularly efficient, with many redundant large-scale balls. Instead, the cover tree is defined as union of dyadic cones with adaptive ranks. Each rank is chosen to be minimal while still covering each point at all scales:
Definition 22 eeaguenniallly-oostteetet cover trees). Let (X, p) have unit diameter and A (ax)s be a dataset X' without duplicates. The cover trees (Cx), ) with insertion ranks (Lt)s are defined:
C = cone(a1; In),
L = 0,
C₁ = C U cone(ag; L&);
L = min E no ball of radius 2 Ck-1 contains z}.
We say that ag was inserted into the cover tree the Lath rank.
Points in Agk are covered by the cover tree C2 at all scales. All other points are also covered by balls in the doubled cover tree, where the radii comparable their distances Agk.- In partieular, define a cover-tree neighbor map C₁ X' Ack - C2 as any one satisfying:
c (x) = ra,
x E Ba,, 2r) and r/2 S p(a, Agk) <r.
(7)
The following lemma shows that such map always exist.
Lemma 23. The cover tree for Ack has a cover-tree neighbor map Ck-
Proof. Let 2 E X Agk and let a E Açk be a nearest neighbor, that p(x, a) p(z, Agk). There exists E E N such that (-+++) p(a, a) < 2- since is not in Agg- As is covered at all scales, there is a ball B C2 of radius 2 that contains By triangle inequality, is contained in 2B. O
Later, we shall also make use of the rooted tree structure on & induced by the cover trees:
Definition 24 (Tree structure). For the above sequence of cover trees and insertion ranks, we let a be the roor of A. For all k > 1, there is ball Baay, 2 La 1 E Cx-1 containing ag. We assign such an aj to be the parent of ag. and rank to the same parent is called a generation of children. The number of generations of children ok has at time n defines the upper triangular array (Gk,u)
say that ag its child. A set of instances inserted at the same
k
L ag is the parent of ag where k' S <n]]-
Application nearest neighbor analysis Let (C&)a be a sequence of cover trees for the sequence of indicated instances A = (Xr,).. Using cover-tree neighbors, we obtain a decomposition of the event that an indicated instance is nearest neighbor (Lemma 25). Whereas the earlier Voronoi decomposition proposed in Equation (6) corresponds to the partition of X' induced by the nearest neighbor map, this one is induced by the cover-tree neighbor map given by Equation (7).
Lemma 25 (Cover tree decomposition). Let (X, p) have unit diameter, let X be a process in X, and let Il be an indicator process. For any n, let C be a cover tree for X [[[= with cover-tree neighbor map c. Assume that Xn & [[Ien] is not equal to one of the indicated instances. Then:
{ Xr EX c U
{Xn is werr/-ssppaaate from Ven and c(x,) = B(a,r)).
Bla.r)eC
In particular, the event within the union indexed by B = B(a,r) E is contained in E B2Brr
Proof sketch of Theorem 17. Fix N. Let C be cover tree for X [[ A purely metric bound is:
N
(
Σ
8a x
[1c)
Σ
E r/2 occurs)
B.EC
(4t)
(111)
1 22, occurs) < 22d |C).
B.EC n=1

---

Here, (i) follows from Lemma 25, where B, denotes ball of radius r in C, (ii) is a larger summation, and (ii) applies the metric bound Lemma 20 and the fact that X' is d-doubling space.
Of course, this bound is vacuous since the cover tree has infinitely many balls. Instead of paying for every ball in C via the metric bound, we can decompose C. into two pieces: relatively slow-growwn collection of large balls for which we apply the metric bound, and a collection of dyadic tails with small combined measure. In particular, we adaptively adjust the tail for each indicated instance so that the combined tail events always have v-mass at most 8. As X is uniformly dominated, the asymptotic rate at which the tail events occur is no more than E(6).
The basic idea for choosing the tails is this. First, when an indicated instance is inserted into the cover tree, we immediately shrink the tail of this new instance by removing O( log 5) of its largest balls, where (c, d) are the parameters associated to the upper doubling condition. Secondly, if this new instance is the first of new generation of children, tail of its parent's dyadic cone. We account for the events corresponding to these removed balls via the packing bound, contributing 2nd to the finite bound per removed ball. The indicated instances appear at a rate asymptotically bounded by y, so the cumulative packing bound grows at a rate of O 22d log )) Treating and d as constants, we obtain an overall bound of:
also remove the largest ball from the
1 A/ N
E [X[en]] = (1108 1 + =(6)
lim sup N-000
See Figure 3 for picture. Mathematically, we select the rank Tk.n of the tail of the kth indicated instance at time n as follows. Let I& be the insertion rank of the kth indicated instance and let k(n) be the number of indicated instances that have arrived by time n. Set the rank to:
g e
Tk.n = L + 1
+
GkAb())-
(8)
g
Lemma E.1 shows that this choice ensures that the combined tail event has v-mass at most 8.
7
Related work
Nearest neighbor rule The nearest neighbor rule and its generalizations form a fundamental and well-studied part of non-parametric estimation, where the vast majority of work considers the i..d setting (Fix and Hodges, 1951; Cover and Hart, 1967; Stone, 1977; Devroye et al., 1994; Cérou and Guyader, 2006; Chaudhuri and Dasgupta, 2014). Also see the surveys Devroye al. (2013); Dasgupta and Kpotufe (2021). Far less is known in the non-i.i.d. setting. For positive results, Holst and Irle (2001); Ryabko (2006) relax to conditional independence where there may be a distinct distribution over instances per class; Kulkarni and Posner (1995) study arbitrary processes. Blan- chard (2022) shows negative result: in some non-worst-case online settings where other learners succeed, the nearest neighbor learner may fail. In the batch learning setting, Dasgupta (2012) and Ben-David and Urner (2014), considered consistency when training and test data distributions differ.
Non- worstwost- online learning Our results echo a motif of smoothed analysis (Spielman and Teng, 2004): worst-case analyses of algorithms yield safeguards by refraining from making difficult- to-test assumptions, but they can be overly-pessimistic and fail to explain the observed behavior of algorithms (Roughgarden, 2021). Recently, two independent lines of work have emerged, introduc- ing new classes of constrained stochastic processes for non-worst-case online learning: smoothed online learning (Rakhlin et al., 2011; Haghtalab et al., 2020, 2022; Block et al., 2022), and opti- mistic universal learning (Hanneke et al., 2021; Blanchard and Cosson, 2022; Blanchard, 2022). We connect the classes in these work through the strictly increasing chain of stochastic processes:
i.i.d. C smoothed C uniformly dominated C ergodically dominated C C1 C arbitrary.
To summarize the behavior of the nearest neighbor rule in these settings, (a) we characterize when the nearest neighbor rule is consistent for arbitrary sequences (Proposition 2); (b) Blanchard and Cosson (2022) shows that the nearest neighbor process not universally consistent for the C1- processes defined by Hanneke (2021); (c) we show, via a new and simple proof, that the original Cover and Hart (1967) Fo-consistency result for i.i.d. processes actually holds for a much larger class of ergodically dominated processes (Theorem 7): (d) we show universal consistency in up- per doubling spaces for uniformly dominated processes (Theorem 12); and (e) we prove rates of convergence for smoothed processes in doubling length spaces (Theorem F.2).
10

---

Acknowledgments and Disclosure of Funding
We thank the National Science Foundation for support under grant IIS-2211386
References
Shai Ben-David and Ruth Umer. Domain adaptation-an can quantity compensate for quality? Annals of Mathematics and Artificial Intelligence, 70(3):185-22 202, 2014.
Alina Beygelzimer, Sham Kakade, and John Langford. Cover trees for nearest neighbor. In Pro- ceedings of the 23rd international conference Machine learning, pages 97-104, 2006.
Moise Blanchard. Universal online learning: An optimistically universal learning rule. In Confer- ence on Learning Theory, pages 1077-1125. PMLR, 2022.
Moise Blanchard and Romain Cosson. Universal online learning with bounded loss: Reduction to binary classification. In Conference on Learning Theory, pages 479-495, PMLR, 2022.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as
easy statistical learning. In Conference Learning Theory, pages 1716-1786. PMLR, 2022.
Frédéric Cérou and Arnaud Guyader. Nearest neighbor classification in infinite dimension. ESAIM: Probability and Statistics, 10:340-355 2006.
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 infor- mation theory, 13(1):21-27, 1967.
Sanjoy Dasgupta. Consistency of nearest neighbor classification under selective sampling. In Con- ference on Learning Theory, pages 18-1. JMLR Workshop and Conference Proceedings, 2012.
Sanjoy Dasgupta and Samory Kpotufe. Nearest Neighbor Classification and Search, page 403-423. Cambridge University Press, 2021. doi: 10. 108637435.024,
Lue 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.
Luc Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, vol- ume 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 -49-0444, Report 4, Contract
314) 1951.
Mikhacl Gromov, Misha Katz, Pierre Pansu, and Stephen Semmes. Metric structures for Rieman- nian and Rin-mmmmnnnann spaces, volume 152. Springer, 1999.
Nika Haghtalab, Tim Roughgarden, and Abhishek Sheuty. Smoothed analysis 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. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 942-953. IEEE, 2022.
Steve Hanneke. Learning whenever learning is possible: Universal learning under general stochastic processes. Journal of Machine Learning Research, 12 2021.

---

Steve Hanneke, Roi Livni, and Shay Moran. Online learning with simple predictors and a com- binatorial characterization of minimax in 0/1 games. In Conference on Learning Theory, pages 2289-2314, PMLR, 2021.
Juha Heinonen. Lectures on analysis metric spaces. Springer Science & Business Media, 2001.
M Holst and A Irle. Nearest neighbor classification with dependent training sequences. Annals of statistics, pages 1424-1442, 2001.
Tuomas Hytönen. A framework for non-homogeneous analysis on metric spaces, and the rbmo space of tolsa. Publicacions Matematiques, pages 485-504, 2010.
Sanjeev Kulkarni and Steven E Posner. Rates of convergence of nearest neighbor estimation under arbitrary sampling. IEEE Transactions on Information Theory, 41(4):1028-100) 10008, 1995.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic and con- strained adversaries. arXiv preprint arXiv: 2011.
Tim Roughgarden. Beyond the worst-case analysis of algorithms. Cambridge University Press, 2021.
Daniil Ryabko. Pattern recognition for conditionally independent data. Journal of Machine Learning Research, 7(4), 2006.
Daniel A Spielman and Shang-Huu Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 5163)3885-463, 2004.
Charles J Stone. Consistent nonparametric regression. The annals of statistics, pages 595-620, 1977.
Michel Talagrand. Maharam's 's problem. Annals of mathematics, pages 981-1009, 2008
12

---

A Proofs for Section
Proposition 2 (Non-convergence in the worst-case). Let (X, p) be totally bounded metric space. Given X - Y, there is a sequence of instances (Xn)n on which the nearest neighbor rule is not online consistent on n if and only if there is no positive separation between classes:
inf ((x)/1(a")
p(a, x') O.
Proof. Suppose that there is positive separation between classes, that margin,,x) > >> 0 for all E X. By Lemma 10, the collection of open balls (xx, c/3) for all X' forms a cover of X by mutually labeling sets. Because X' is totally bounded, there a finite subcover of by these mutually labeling balls. By Lemma 9, each of these sets admits most one mistake, so the nearest neighbor rule makes at most finitely many mistakes, achieving online consistency.
On the other hand, suppose the class are not positively separated. We claim that there is a sequence of pairs (X2n+1, X2++2) where a nearest neighbor of X2n+2 has different label:
(22+22) + n (2222))
On this sequence X, the nearest neighbor rule makes a mistake at every even time step, so that:
N
lim inf N N nml
1
Σ (n)(x)) * m(xx)) + 2
1
fails to be online consistent on (X,
To prove the claim for fixed First, define the minimal non-zero interpoint distance in X<2n:
min {p(z,z')=2 # z' and 2, x' {- Let x, x' X have different labels and p(x, x²) < r/3. There are two cases:
The points x and have distinct nearest neighbors & and H' in X Then, the triangle inequality shows that:
p(ū,x) + 2(x,2') + p(x', x)) 2 ((2 2
Since p(x,x') < r/33, we obtain that:
p(x, 3) p(x', (('',""' 8¹)
> r/3.
2
This implies one of p(x, I)) or p(z', x²) is strictly larger than /3. Without loss of generality, let p(z', ,5) r/3. Then, set X2 unique nearest neighbor X2n+1, which has a different label.
and X2n+2 x'. In this case, X2n42 has the
The points and x' have the same nearest neighbor in Z. Then, by exchanging and x' if necessary, we have that 17(2) # (1x)). Set X2n+1 and X2n=2 x'. The nearest neighbor of X2 is either X2n+1 or 2. Both have different label than X
13

---

B Proofs for Section 3
Lemma 5. Let X be uniformly dominated by v at rate =(6). and let (Fn)n be its natural filtration. Let An be an Fa-predictable sequence where lim supn-+od (AA)) < almost surely. Then:
limsup N N
3 1(x, An) - =(6) N
a.s.
Proof. The following sequence (Zn)n is martingale-difference sequence:
Zn 1(X, An) Pr (Xn An Fn-1).
We obtain:
N
lim sup N-000
Σ 1[x, An)
lim
Σ
Zn
lim sup sup N
1
Σ Pr (Xn An Fn-1),
N
N
(a)
(b)
where (a) converges by the martingale law of large numbers, and (b) is bounded by s())
because the uniform domination implies that:
lim limsup sup Pr (X, E An Fn-1) < =
a.s.
n-000
For completeness, we include a version of the strong law of large numbers (SLLN). Theorem B.1 (Strong law of large numbers for martingales, (Durrett, 2019, Exercise 4.4.11)). Let (Ma)az be martingale and let Zn M, Mn for n > EZ K < co, then:
Ma/n - 0 a.s.
14

---

Figure 2: (Left) A visualization of mutually-labeling set (orange ball). There are two classes (dark and light gray) separated by decision boundary (blue line). The length of the dashed line measures the margin of a point in the set. The length of the dotted line is bounded above by the diameter the set. (Right) An example of a collection of labblllig sets (dark and light blue balls) covering all but a region of small mass. Since the nearest neighbor rule makes at most one mistake per ball, eventually all mistakes must come from the white, uncovered region.
C Proofs for Section
Lemma 9. Let U be mutually-labellin set for n. Let X. be arbitrary process. Then:
Σ 1 1 EU and ((,)). + (Xx)) 1
Proof. For the sake contradiction, suppose that there times n m for which the indicated event occurs. In particular, X,, Xm U and a mistake was made on the latter point:
n(Xm) + m(Xm).
As both are contained in U, we have:
p(Xm, Xm) S p(Xm, Xn) & diam(U).
On the other hand, the margin of Xm is upper bounded:
mXrgin, p(Xms X
Together, they contradict the mutually-labeling property of U.
Lemma 10. For any 0 < < (x))3 the ball B(x, r) is mutually-labeling for n)-
Proof. Let x' E ((r,r). Since x' is within the margin of xr they must share the same label. For any point z from different class f/))) F nTx), we obtain by the definition of the margin z:
margin,, (x:) p)x,
Subtract p(x,x') from both sides and apply the triangle inequality p(x, p(x,,²) s p(a', 2):
margin, (2) r/3 < p(a',2).
Finally, taking infimum over all points in other classes implies:
2 margin, (x) < margin, (x').
On the other hand, the diameter of the ball (xx,r) r) is at most 2r < 2 (x) Combining this with the above proves that B(x, r) is mutually labeling.
15

---

D Proofs for Section
Proposition 13 (Fo is dense in L.), Let ,X V) be a metric measure spaces where p is doubling and v is finte Borel measure. Then, the set Fo is dense in L, V).
The proof of this follows the standard approach: for any 1j E (X v), we can construct countable partition of almost all of X' such that y) overwhelmingly assigns each partition the same label, by which we mean up to a ò-fraction of that partition. The existence of such partition requires a version of the Lebesgue differentiation theorem. The theorem in basic settings applies to doubling metric measure spaces (e.g. Heinonen (2001)), in which all balls satisfy the doubling property:
(B 2r)) & Cv(B(zrr))
As our setting only assumes doubling metric space with a finite Borel measure (not necessarily doubling measure), this property is not guaranteed to hold. However, Hytönen (2010) shows that there are still a plethora of balls that satisfy such property, which is defined as:
Definition D.1 (Doubling ball, Hytönen (2010)). Let p, be metric measure space. We say that ball (x) in X' is (ax, (3) doubling for some B whenever:
(B(x, s (B(,
To prove that Fo is dense in L', we apply a version of the Lebesgue differentiation theorem re- stricted to (5, dd-ublig balls in space (Theorem D.2). This is followed by a corresponding Vitali covering theorem for such balls (Theorem D.3). With these ingredients, the proof is routine:
Proof. Let P)) and fix O. We show that can construct function v/' Fo with negligible boundary such that || - 11'll'' < 6.
To do so, make use of a version of the Lebesgue differentiation theorem for doubling spaces with finite Borel measures, Theorem D.2. states almost every x E X has a positive sequence I' J such that the following Lebesgue differentiation condition is satisfied:
J J ((](z) + n(=)} v(dz) =
lim 1..00 v v(B(E, rw))
and where all balls B(x, rw) are (5, B))-duublin Let's denote by Leb(r)) the set of points satisfying choose ball B(z, rx) that is
this Lebesgue condition. In this case, for each z e Leb(n), (5, douubligg and whose labels overwhelming agree with (z)):
((((x) + n(z)) v(dz) 88
v (B(x,Tw) (w)) B((..ra)
By Theorem D.3, which is a version of the Vitali covering lemma for collections of (5, -ouubling balls, there is a countable disjoint subfamily of balls C C. {B(x,rx) x Leb(n)) that covers almost all of X. Enumerate the balls in by B(z,, Tz), and define the function:
Σ ((xa) B(a.))))
By the dominated convergence theorem, have that ||n n' ( < 8. Furthermore, points in the balls B(x,, rx) are not boundary points; 1/ has negligible boundary.
Theorem D.2 (Lebesgue differentiation theorem, Corollary 3.6, Hytönen (2010)). Suppose that (X, p. v) is a metric measure space where p is doubling metric and v is finite Borel measure. There exists x E X. there exists a positive sequence Tn 0 such that:
such that the following holds. Let 1) I. (,, v) be bounded. For v-almost every
lim v(B(Irra) S ndv,
<(x))
re.0
and the balls B(x, Tn) are (5, doubbligg
16

---

Theorem D.3 (Vitali covering theorem, Theorem 1.6, Heinonen (2001)). Let (X, p. be doubling metric space with a funite measure. Let > Let A X be any set and let FF be any family of balls such that for each x. E A, there exists some sequence In + 0 where:
E and
B(,,Tn) is (5, B) doubling.
Then, there is countable disjoint subfamity of F that covers v-almost all of A.
This is slightly more general version of the Vitali covering theorem than given by Heinonen (2001), although is implied by the proof given there. In that proof, the sequence of (5, -d-ubblin balls was deduced from stronger condition; here, we directly assume its existence.
Lemma D.A. Let (X, p.v) be metric measure space where v is finite Borel measure. Suppose that X is a process that is uniformly dominated by at rate E(8). For any ε > 0, there exists a region X C X with bounded diameter such that:
limsup N-+00 N
Σ
1 & Xn $ x3 <
a.s.
Proof. Fix 0 < < Let > 0 be sufficiently small that E()) < E. Let X. For any positive sequence 50, the balls converge B(x, ra) 1 X. As is finite, by the continuity of measure, there is sufficiently large rn such that vBB)
6, where
B(x, rn). Let X' 3B.
Suppose that = min(n h:: X, E B) is the first time that X, hits the ball B. By Lemma 10, the ball B has the mutually-labeling property for the function 13.. Thus, for n > т, whenever the nearest neighbor falls outside 3B, this implies that X,, falls outside of B. It follows that the chain holds:
Vn T,
(X, $ 3B} C {Nn $ B}.
And as we also have (X, 3B} C (X,, & B), the bound follows:
N Σ n=T+1
Σ n=1
1x,, $ X' or Xn & x3) s (TAN)+
1(xm BJ.
The stopping time is almost surely finite. The Canee-Cantelli lemma shows that is almost surely eventually bounded above by some n E N, since the following sum converges:
X n BB= < (1--)-=-== 1 E
Σ Pr (r =
n=1
n=1
Thus, the asymptotic rate of X or X escapping X' is bounded by the rate at which avoids B. By Lemma 5, this is at most e.
Theorem 14 (Ergodic continuity of nearest neighbor processes). Let (X, p,v) be a upper doubling space with bounded diameter. Suppose that a process X is uniformly dominated by u at rate e(0). There exists constants C1, C2 such that for any measurable set A X with v v(A) do.
N 1xx EA] < inf 020
(11
{
1 =(6)) + +c(0)}
lim sup No
Σ n=1
8.8.
Proof of Theorem 14. Fix any measurable set A C X where v(A) < 6p. Define the indicator process by I, = 1(X,, E A}. Lemma implies that I is asymptotically e(6n)- Then, Theorem 17 immediately implies that there are constants C1,02 c2 such that:
N Σ
188 E A} < E(6)) (ar + c2 log 1 + +00)
lim sup
a.s.
N
N N-0
7=
Optimizing the bound implies the result.
17

---

E Proofs for Section 6
Theorem 17 (Long-term influence bound). Let ,.P,) be bounded, upper doubling space. There are constants C12 C2 > 0 so that the following holds. Let X be uniformly dominated at rate E(6) and let Il be an indicator process adapted to X asymptotically rate-limited by R O. For any å > 0, the rate that the indicated instances X [[[cn]] contain nearest neighbor Xn is at most:
1 N n=1
Ei [[[en]] <7 (at log 2) + E(0) a.s.
lim sup
N-+00
Proof of Theorem 17. By rescaling, we assume without loss of generality that X' has unit diameter. Recall from Definition 15 that given an indicator process we defined k(n) to be the counter for the number of indicated instances up through time n, and т& to be the time of the kth indicated instance. In particular, we have by assumption that lim sup k(n)) < y almost surely.
Let (C*)a ) be chain of scquentially-consttuutte cover trees associated to the sequence of indicated instances (X )x. Let La be the insertion rank of the kth indicated instance Xr Recall that this means that Cg is constructed by taking a union of Ck-1 with the dyadic cone centered at Xx, of rank Lg. For the kth indicated instance and for all time n 2 Tk. define the tail rank T Tk to:
Tk = LA + 1+
lg
+ Gk,K(m):
(8)
where (c. d) are parameters associated to the upper doubling condition, and &k,,(n)) is the number of generations of children it has by time n. Let's define the --tail of the cover tree at time to be the union of the rank-(Tk,n + 1) tails of Xx, and let An be the union of the doubled balls:
k(n)
Ta =
cone ;T +
and
An = U 2B.
BET,
By Lemma E. the mass of the tail is (A,)) < 5. We now apply Lemma 25 to bound the number of times an indicated instance is a nearest neighbor. To do so, we need that X,, is almost never contained in X[[<o]] This follows from the upper doubling condition, which implies that singleton sets have zero mass. By uniform domination, X,, is almost surely never equal to a previous instance. And so, Lemma 25 implies that:
U B.ET.-1
En
B2Brr/2 C {Xa E An-1)
a.s.,
and that almost surely:
N
N Σ 1n E An-1). 1=1
Σ 1 {xx E
x [
S
Σ
HE2Br.r/
occurs}
+
==1
n=1
B,ECe(n 1)\Tn-1
(a)
We bound (a) and (b) separately:
The first term is bounded by Lemma 20:
(a) S Σ
Σ 1 { (E2B,..) r/22 occurs] < 2dd .CR(N)) \ Tw/
B.ECuN TN R=1
The number of balls in CR(NN) TN can be computed by counting for each indicated instance the number of balls not in its (TR,N 1)ttail:
A(N)
A(N)
(ThN + -1 LA = k(N)
+
ig
+
GRA
1g C
$ A(N).
2++
+ A(NN,,
18

---

Figure 3: The left, middle, and right figures shows the cover trees for the first three indicated in- stance (X,, X Xyy), along with their metric and measure bound trade offs. Each concentric disk corresponds ball the cover tree, and the orange disk corresponds instance. The tails are chosen so that the y-mass of the orange region remains bounded by 6.
tail for an indicated
where the last inequality holds because the total number of generations of children is no more than the number of nodes in the tree. As the indicator process is asymptotically rate-limited by % we obtain:
N
1 EB.r/2 occurs} < < 22d (3
Ig 1 a.s.
lim sup N0
Σ ==1
Σ
3
N
(b) Since the mass of the tail is bounded (An)) < 8, the second term can be asymptotically controlled on average by Lemma
N E1(x, E An-1] S <E( a.s.
1
lim N
N n=1
Summing these bounds and choosing C = 22d (3
Ig c) and c2
2d completes the proof.
Lemma F.1 (Cover tree d-tail). Let (X, p. v) a upper doubling metric space with unit diameter. Let (Cx) be chain of cover trees for the sequence A (ax)k and let (Lx) be its sequence of insertion ranks. Define the array of tail ranks (Ten)ssn and tail sets (An)m
Tk.n = L
1g
+ GR.
and
A, =
U 2 T-Te).. k=1
d
where d is the doubling dimension and is the upper doubling constant in Definition 11, For all n, the mass of the tail is bounded v(A,) < 8.
Proof. Fix n and S Agn a generation of children with rank L. This set instances along with their parent forms a 2- packing of a 2-L-1 ball. Therefore, |S| s 2d since X' is doubling.
We extend S to include all its descendants: let S be the subset in Agn that contains S and has the property that if x' is child of S, then x' S. Let the tail centered be the following union:
As,n
U B(ax, 2-Tm.). a&ES
In partieular, when S {a1), then = and S {a), (dl...., an) )- It suffices show:
v(As,n) 5 8. ddd
We proceed by induction on the rank T. in decreasing order.
19

---

Base case: let L be the maximal rank of any instance in Acn and let S be any generation of children with maximal rank. These instances have no further descendants, so S S. For each E S. we also have Gk.n = 0. By union bound:
((As.)) c2 S 8..2-d.
0,
where the first inequality uses the measure condition of upper doubling spaces, and the second inequality follows from our choice of Tk,n and that [S| 2
Inductive step: suppose that the claim holds for all generations with rank é > L. Let S be any generation with rank L. For each ag E S, let GR.n be the collection of its generations of children, which all have rank strictly greater than When S' I3.0 is generation, let S' extend S' with its descendants and I(5") be the rank of S' Then:
As.a U
2(a2.2-Tu.1) U U Ast.
S'E0k.
By the inductive hypothesis, have:
(4)
v(As,n)
S
Σ
5-2-d(1-Lett
+
Σ S'EGk.n
8 8.2 2-d((5)
RxES
(6)
Σ Σ
2- (18)
6
2 2-d(L++) (iv)
I 5.2 dl
1 1 2-d
a2ESE>L
where (i) follows by union bound, (ii) by the inductive hypothesis, (iii) by the geometric series formula, and (iv) by the upper bound that |S| < 1d
Lemma 20 (Packing bound). Let (X, p) be a metric space, U C X be subset, and r > 0. For any process X. the number of (U, sepparredd events is bounded by the r-packing number of U,
Σ 1 occurs) SP.UU.
Proof. Let Z C. X be the collection of instances Xn E U with nearest neighbor distance at least r:
{Xn, p(Xn; Xn) r).
Fix such that Z. For all X,m E Z where m < n, we have:
p(X,, X,n) 2 (nn, Xx) 2 r.
For all Xm E Z where m n, we also have:
p(Xn, Xm) 2 p (Xm, Xm) Zr.
Thus, Z is an r-packing of the set U, and so P.(U).
Lemma 25 (Cover tree decomposition). Let (X, p) have unit diameter, let be a process in X, and let I be an indicator process. For any n. let C be cover tree for X X[Lcn] with cover-tree neighbor map c. Assume that Xn, & [[Icn] not equal one of the indicated instances. Then:
{nn [x=X(Tl]]] c U
{Xn 1/22s//2-sppaaat from Xenn and c(X,,) B(a,r)}-
B(a.r)ec
In particular, the event within the union indexed by B = B(a,r) C is contained in E BB.rr22
Proof. Let cu (n.) ) B, be an r-ball. Then, by Equation (7), the definition of a cover-tree neighbor, we have that X, is r #/2-separated from X[I[s]] When the indicated instances contain a nearest neighbor, then n is also r/ r/2-separated from Xzn- By the other condition of a cover-tree neighbor, we have that X,, E 2B, Together, this implies the (2B,, (BBr,r/2)-seaareee -separate event.
20

---

F Rates of convergence for smoothed processes
In this section, we show that our proof techniques can be extended to obtain rates of convergence for uniformly dominated processes. Recall that our basic strategy in Section 4 was to decompose A' into two pieces: (i) a region that a finite union of mutually-labeling sets and (ii) remainder As with small mass v(As) < 6. When 7) E Fo has negligible boundary. then 5 can be taken to be arbitrarily small: this is possible because points that cannot be covered by mutually-labelinn points, which have measure zero. We can adapt this idea to yield rates by quantifying the number of sets required to cover all but a region of 6-mass. To this end, we define:
sets are boundary
Definition F.1 (Murually-labeling covering number). Let V X. The mutually-labeling covering number (,,.,((V) for is the size of a minimal covering of V by mutually-labelinng sets of r).
Then, an expected mistake bound on a process X that is uniformly dominated at rate e is obtained by separately counting mistakes on V and VS, where we bound mistakes (i) on V by its mutually-labeling covering number and (ii) on ve by its v-mass:
Σ (m(()) + ((X))) min {
(M.., NN-)=()
N, inf vex
By standard application of Azuma- Huuma-Hoeffding's we can convert this into high-probability bound:
Theorem F.2 (Convergence rate). Let PVV) be metric measure space with separable metric p and finite Borel measure v. Let be measurable and let % be uniformly dominated by v at rate s(ő). Fix p > With probability least 1-p, the following holds simultaneously for all N :
2N
Σ # # ((Xn)) S min N, inf VEX
(ML.,(V) N -N=((V(V)) 2N log
p
Of course, this bound could be vacuous, for example if every point of 1j is a boundary point. In the following, we restrict ourselves a setting with stronger stochastic and geometric assumptions. This allows us to provide quantitative bounds on the two terms VaLL,,(V' and c(v(V)) in Theorem F.2 For this stronger setting, we obtain a convergence rate Theorem F.5 by balancing these two terms.
F1 Convergence rate for smoothed processes in length metric spaces
Here, we consider a class of uniformly dominated processes with a stronger condition that is often studied in smoothed online learning. They satisfy Lipschitz continuity with a rate e(5) a o- 5: Definition F.3 (Smoothed process). Let a > 0. A process X is a-moothhed with respect to v if:
Pr (Xn E A xxn) S - v(A), VAC X.
We also work in length spaces (Definition G.8 or Gromov et al. (1999)), in which distances be- tween points are given by the infimum of lengths over continuous paths between those points. The appealing property of length spaces is that the margins of points are equal to the distance to the boundary:
Lemma E.4 (Margin in length spaces). Let (X, p) be length space. Let n be a function. Then, margin, (x) = p(x, 0)
In this case, it is natural to restrict V X' in Theorem F.2 to the sets of the form:
v= x E X margin, (x) 2 r).
These are the set of points whose margin is at least r. Then, we need to control the labull-labeling covering number of V, and the u-masses of V.S. When X' is length space, these can be bounded terms of the geometry of the boundary 0X. The reason that in length spaces, points with small margins are also close to boundary points: here, Ve precisely coincides with the r-expansion 0,2" of the boundary. And when X' is a doubling space, we can quantify the bounds in terms of the box-counting dimension b(O,,)) and the Minkowski content m m(0, of the boundary.
21

---

In particular, Proposition G.9 shows that for small r.
Na (V.) rr and
(V, S m r,,
(9)
where the hand-waving inequality can be made rigorous by replacing b = (1) and m = m+) For example, this yields convergence rates on smoothed processes, by plugging Equation (9) into Theorem F.2. For simplicity, assume that b so that the O((2N log N) term is lower-order. After optimizing r, we obtain the following result:
mmN b/(b+1)
# mistakes at time N S
Theorem F55 (Convergence rate for smoothed processes). Let (X, p.v) be bounded length space with a doubling metric and finite Borel measure. Let 1J E Fo. Let X be o-smoothed process. Suppose that the boundary dz has box-counting dimension b > 1 and Minkowski content m. For any choice of (1, c, > O, there exists constants Co. C1 > 0 such that with probability at least 1 p, the following holds simultaneously for all N N:
(m + N2)NN (b+er)/(b-1)
Σ
+ + ((x)) S +
G Proofs for Appendix F
Proof of Lemma F.4 To show that mz(x) = p(z, 0x),, we prove left and right inequalities.
First, the margin is upper bounded by mx(x) S p(x, ax). To see this, fix 5 >> 0. By the definition of the distance between and the set 0x, there is boundary point 8X such that:
p(x, < p(x, 0x)
2
And as boundary points are arbitrarily close to at least two classes, there exists x' E X close to z:
8 pZ ~
while also belonging different class than æ. By the definition of mz(z) and by triangle incquality, we obtain that for all d > 0, there exists some x' satisfying:
me(x) S p(x,2') < p(z, 0x) + 8.
Letting ō to zero yields the first inequality.
For the other, we claim that 7 [0, 1] + X' is a continuous path from x x' with c(x) + c(x'), then there exists a point >(t) contained in 0x. If the claim is true, then the other incquality holds:
( p(x, 0x) <
inf inf E(T) c()))((()))
(18)
inf p(xxx') o(2))
(181)
mo(x),
where (i) the infimum above is taken over all continuous paths from & to x', (ii) applies the definition of a length space, and (iii) applies the definition of the margin.
To prove the claim, let f be the first time a point on the path has a different label than æ. Formally,
arg inf {c(r(s)) + c(x)}
sE
To show that (t) E 0X, we need to exhibit a point y(s) that is 8-close to yt) with a different label, given any O. Indeed, such a s exists by the definition of and the continuity of 7.
To obtain bounds on the mutually-labeling covering number NV,..VV,), we need to introduce the notion of the box-counting dimension a set A X and the doubling dimension of metric space X. Let us first recall the following definitions and results from analysis and measure theory.
Definition G.1 (Covering number). Given r > and A X, the r-covering number NG (G(A) of is size of minimal covering of A by balls with radius
22

---

Definition G.2 (Box-counting dimension). The (upper) box-counting dimension of A C X' is:
log (AA
b(A) lim r-+
log 1/r
The box-counting dimension implies a bound on the covering number (A) of -bb()))(01) The following lemma is straightforward conversion of the asymptotic limit into quantitative bound.
Lemma G.3 have box-counting dimension ((A). Then, for all c > O, there exists a constant C > such that:
upper bound on N,). Let X be bounded with diameter R. Let A C X
NA( < Cr (b(4)+t))
Proof. Fix 0. By the definition of b(A), there exists ro such that whenever < To.
log (A) log 1/r
< ((A) +
Because (aaauseNN((A)) (A) is non-increasing in r, we can extend the bound to all 0 <r<< R.
log (Ag log Ar()
< b(A) +
where Aro ro) In fact, we have min(r, > r ro/ R, and so:
N1(A) <
Tb
-(6(A)+o)
R
To finish the proof, it suffices let C = (ro/R) (b(A))c),
Lemma G.4 (Lemma 2.3, Hytönen (2010)). Let (X. p) be doubling with doubling dimension d. There exists constant C' such that for all balls (Ix, r), the covering number is bounded:
Ne/2(B(a,T) -2.
To obtain bounds on the mass (VV)), we need to introduce the Minkowski content of a set A C X. First, recall that the r-expansion of a set A fattens the set to points of distance within r of A:
Definition G.5 (r-expansion). Let A X be a set and 0. The r-expansion A" of A is:
A" U B(a,r).
The Minkowski content of the rate at which an infinitesimal fattening of increases its mass: Definition G.6 (Minkowski content), Let (upper) Minkowski content of A X' is:
"(A") v(A)
(AA) lim sup
r-0
r
The following lemma bounding the covering number of the r-expansion of set in terms of the doubling dimension will also be helpful:
Lemma G.7 (Covering the r-expansion of a set). Let (X, p) have finite doubling dimension There exists constant C 0 such that for all A X, we have:
N,(AA) S C2)N,(A).
Proof. Let A be covered by the balls B(x ..., B[En, where n = (A)) Then, by the tri- angle inequality, the r-expansion A, is covered by the r-expanded balls, B(xi, 2r)...,, B[x,, 2r). Now, by Lemma G.4, each expanded ball B(x,, 2r) can be covered by C2d balls with radius It follows that covering A, needs at most " balls with radius r.
23

---

G.1 Bounding geometric quantities of O
Definition G.8 (Length space), metric space (X, p) a length space if for x, x' E X,
p(x, = inf {(7),
where y: [0, + X include all continuous paths from to x' and E(7) is the length of the path 7. Proposition G.9 (Geometric quantities of 0x). Let p.. be a bounded length space with firite doubling dimension and Borel measure. Let Fo- Then, for any C1,02 0, there is constant C O and ro > O so that for all 0 < < To,
NMLLn (V+) S (r-(b(0,)))tt)
and v(V.) 2 (m(0, + 02)
Proof of Proposition G.9 Recall that V,, and 0X are defined in terms of the margin:
V = (x X margin, 2 2r and 0x = fx X margin, 0)-
While the complement Ve always contains the expansion 0,, generally V, can be much larger. But when X' is a length space, equality holds: Lemma G.10. Let (X, p) be length space. Then, for all r > 0:
Ve 0y2t.
Proof. Lemma F.4 shows that when X' is a length space, margin, (x) p(x, 0,, Thus: ((x,0X) <r
x E V
margin,, <
x x OX..
The question of bounding NI (V+) and (VV") becomes that of NML (X 8)) and v"), Proposition G.11 (Upper bound on NML). Let X be a bounded length space with finite doubling dimension and diameter R. For Fo. let b be the box-counting dimension of dnx. Then, for any 0, there exists a constant C > O such that for all > O:
NM 0) < CRAd,-(644
Proof. We can write X' 8, union of layers of the form La 2 0x22
Tg R/rl
x x
U
L
k=
Then, can upper bound the mutually-labeling covering number by the sum:
Da R/rl
NML. (X' X²) s
Σ
NM (T&).
(10)
A=
To upper bound NMML(L.) first note that by Lemma G.10.
La C X 0²p Vi+r-
Thus, the margin any point x E Lg is at least rh. By Lemma 10, the ball B(x, 2/33 is a mutually-labeling set, so that NML (Lx) I N2tr (Lx). In fact, we obtain the following:
(1) S N2r-2, (Lxz)
(L) S (2tr/a(LLe)
No. (0x222111
(00
2,23d N2 (0
Ng (0x)
(224d(2++1,)) (b+cc)
(11)
24

---

where (i) holds because the radius 2* is less than r/3 (ii) follows because 0 contains L and so has larger covering number, (iii) makes use of the definition doubling dimension three times to convert the ccoerrin number to -ooverng number, (iv) applies Lemma G.7 to convert the covering number of the expansion to that of the boundary set, and (v) upper bounds the covering number in terms of the box- box-dimension of OX by Lemma G.3.
By combining Equations (10) and (11), we obtain:
NML (X x²) < C32 (b+c) Σ 2 (b+))(++1)
k=0
where the geometric series converges to 2 (b+te) We finish by relabeling the constants.
This shows that (V,) (=(((x))++((1)) Next we show that =(VF) = (m(ax) + o(1) r. This immediate from the definition of the Minkowski content m(0x))
Proposition G.12 (Upper bound v). Let (X, p. be metric Borel space. Let rj E Fo whose boundary dz has Minkowski content m. Then, for any e > 0, there exists some To such that for all 0 <<T' r < TO
v(0x") < (m + cr.
Proof. Since the boundary has measure zero, the definition of Minkowski content states that there exists To so that for 0 < < < To.
v0x"") m(xx) +
The result follows by multiplying through by r.
Together, Propositions G.11 and G.12 prove Proposition G.9.
G.2 Proofs of convergence rates
Proof of Theorem F22 Fix V c X. Let X be uniformly dominated. Denote by A, C X region on which the nearest neighbor rule makes a mistake at time n. We can count the total number of mistakes separately V and Ve:
N
N Σ 1(x, E An}
Σ
((((x)) # ((x)) =
m=1
N
N Σ1 E An nvg.
Σ
1(x, E
mistakes made in V
n=1
mistakes mado in V
At most mistake can be made per mutually- set on V, the first summation can be bounded by NML(V). The second term can be bounded by the number of times X,, hits Vo:
1xx,, E An n V9} < 1[X,= E V3 1[X, E Vo E1{X,, V' E[1 V'-1F
martingale difference
By Azuma-Hooffding's 's we have that with probability at least 1 p2/222
N
2N2 N log
2N
Σ 1xx, - E[L(X, E V= 1=1
<
2N log
p
maniinale difference
Because the process is uniformly dominated, we also have [[ E VCH < ((((V9). By taking a union bound over all E N, we obtain that with probability at least 1 - p.
N
2N
Σ (n((x) + ((x)) < NoL (V) N=(v(V9) +
2N log
p
n=11
The result follows from optimizing V, and by noting at most N mistakes can be made in N time.
25

---

Proof of Theorem E5 Given C1, > 0, Proposition G.9 yields C, ro > 0 so that when 0 < r <
To>
.(V,9) Σ (m- + 02) r. From Theorem F.2, it follows that with probability at least 1 - p. we have for all T:
NM.. (V,) I Cr (b+(b)) and
2N
[n((X,) # m(Xn)) z
inf ocreno
+ + 2N log
p
2N 2N
S inf o<r<<o
Cr-(bta) + No 11 (m 02) +
p
where r is optimized at:
[C(++ 1/(b+o++1
N T(m+
provided that ryy ru- This will eventually hold for sufficiently large N No. For N No. we can use the coarser mistake bound No. Thus, for all N E N:
N Σ + # ((x)) & No + Ci R=1
(mm 02)
(bta)/(b+att))
2NV
+ 2N log
where C1 is constant, defined below.
Because we assumed b > 1, the v log N term is eventually dominated by the X(++o(1))((b+1) term when N Ng is sufficiently large. We obtain the result by setting Co below, and noting that we can simplify the exponent because (b + c/)((b + e + 1) < (6 + c/) + 1).
Cp = No + 2 2Ng log 2Nd
C1 = 2C(b+
26

---

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: There are prior work on the consistency of the nearest neighbor rule in the realizable setting, Both require much stronger assumptions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The assumptions used throughout are clearly described in the theorem state- ments. Additional limitations are addressed in the related work section.
Guidelines:
The answer NA means that the paper has 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 separate "Limitations" section in 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 au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect 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 ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to system might not be used reliably provide closed captions for online lectures because 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 ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
27

---

Answer: [Yes]
Justification:
To our knowledge, the paper is complete and correct.
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 theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is a theoretical work.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data often one good way to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibilityy may be tricky in some cases, in which case thors are welcome to describe 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., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
28

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This is theoretical work.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ca
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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:
//niss http/ubllcgggucce Siliddes/ooeee /oodeSubmisss Submissiiiiss wwwsssssssicoooooooooooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to 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. only a subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as 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: This is theoretical work.
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
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
This is a theoretical work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of eπrоrs 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 enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theoretical work.
Guidelines:
The answer means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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 NeurlPS Code of Ethics https:
Answer: [Yes]
Justification: The Code of Ethics do not seem to apply to this work.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
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: [NA]
Justification: This work focuses on extending our theoretical understanding a long-existing algorithm.
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 spe- cific groups), privacy considerations, and security considerations.
30

---

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 mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility 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:
This is theoretical work.
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 re- quiring that users adhere usage guidelines or restrictions 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 require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: This is paper did not existing assets.
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 the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense 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.
31

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl 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. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the per include the full text instructions given to participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve 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 contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage 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 crowdsourcing or experimentation with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) 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 we 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 as the institution conducting the review.
32


Reviews:
[{"review_id": "KfbEqXpxGB", "reviewer": "Reviewer_LFbH", "summary": "This paper studies the nearest neighbor rule in the realizable online setting and closely checks under what assumptions it can achieve online consistency, i.e. the mistake rate eventually vanishes as the number of samples increases. It proves that for all measurable functions in doubling metric spaces when the samples are generated by a uniformly absolutely continuous process with respect to an underlying finite, upper doubling measure, the online consistency is achieved.", "questions": "Why ergodic continuity is related to uniformly absolute continuity such that it is included in the proof?", "limitations": "Yes, the limitations are adequately addressed. There is no potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "While the prior work showed the online consistency for nearest neighbor rule under much stronger assumptions (instances are i.i.d. or the label classes are well-separated), this paper improves the understanding of this problem by showing it in the uniformly dominated regime. This result potentially gives us an understanding of other algorithms when studying online learning beyond i.i.d. and smoothed adversary settings.", "weaknesses": "While at this point, the review does not notice any significant weakness that needs to be addressed, the writings of the paper could be a bit too technical.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading of the paper and for your thoughtful\ncomments. To address your comments/questions:\n\n0. On the technicality of the writing: thanks for this feedback. We will\n   continue to work on clarifying the exposition.\n\n1. This is a very interesting question. Perhaps the even more \"obvious\" question\n   is: \"why is uniform absolute continuity related to ergodic continuity such\n   that it is included in the assumption?\"\n   \n   At a high-level, the consistency of an online learner is an ergodic—by which\n   we mean *time-averaged*—property of the prediction strategy, since it has to\n   do with the number of mistakes the learner makes on average over time. Then,\n   the reformulated question above asks: why do we need to constrain the way\n   that $\\mathbb{X}$ is generated in a *time-uniform* way rather than just a\n   time-averaged way? The answer, in short, is that two processes $\\mathbb{X}$\n   and $\\mathbb{X}'$ that look the same on average can have nearest neighbor\n   processes that behave very differently (this can be seen as a corollary of\n   Theorem 2 of Blanchard (2022) along with the classical consistency result of\n   1-NN in the i.i.d. setting). \n\n   Interestingly, the need for a time-uniform constraint arises for the problem\n   of consistency of 1-NN for *all* measurable functions. If we restrict\n   ourselves to a smaller class of label functions, we may relax the generative\n   assumptions on $\\mathbb{X}$. For example, for essentially boundaryless\n   functions in the class $\\mathcal{F}_0$ (see Definition 5), it is enough for\n   $\\mathbb{X}$ to be ergodically dominated. And for the class of label\n   functions with positive margin on compact spaces, no assumptions are required\n   on $\\mathbb{X}$ for 1-NN to be consistent, which is shown by Kulkarni and\n   Posner (1995).\n\n   In addition to our specific contributions about the behavior of 1-NN and\n   nearest neighbor processes, our introduction of the notions of uniform\n   absolute continuity and ergodic continuity helps fill in the continuum of\n   types of non-worst-case online learning settings we should study (see also\n   the chain of settings in Related Works section).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VbnJTSABlq", "reviewer": "Reviewer_XeYp", "summary": "This paper considers the consistency (or mistake-bound) of the nearest neighbour rule in the realizable online setting when the instances are not necessarily i.i.d. but drawn from a well-behaved stochastic process. The authors prove that when the underlying stochastic process is uniformly dominated, the nearest neighbour rule is consistent for labeling functions that have negligible boundaries. To prove this they introduce the notion of labeling functions on mutually labeling sets, which they then generalize to labeling functions on upper doubling metric measure spaces. Finally they also give convergence rates for smooth stochastic processes, which is a special case of the uniformly dominated setting considered in the paper.", "questions": "1. The authors mention on line 307 that \"Dasgupta (2012) ....... considered consistency for non-online settings....\" This seems to be a gross oversimplification. I would like a clarification on this point. \nDasgupta (2012): Consistency of nearest neighbor classification under selective sampling, COLT 2012.\n\n2. Do the proof techniques extend naturally to the $k$-NN setup or the $k_n$-NN setup? This is not immediately clear to me from the paper.\n\n3. Do the proof techniques extend naturally to the agnostic case where there is no underlying labeling function but instead $Z_n=(X_n,Y_n)$ are jointly drawn according to some underlying stochastic process $Z=(Z_n)_{n>0}$? The proof techniques would then boil down to computing mistake bound against the Bayes optimal classifier in this case.\n\n4. I am not sure about the significance of Theorem 14 or Section 6, and would like a clarification on the following point. The notion of consistency for uniformly dominated stochastic processes should straightforwardly imply a notion of consistency for stochastic processes which are dominated by much weaker notions of convergence. I suspect that Theorem 15 can be generalized to stochastic processes which are mixing, and the parameter $\\gamma$ can be replaced by some function of the mixing coefficient.", "limitations": "The paper does a good job at clearly specifying the assumptions used in the setup, but sometimes does not address settings which are not explicitly considered in the paper. Please refer to the Questions section for clarifications.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The central question of this paper is very well-motivated and an important question in the online learning literature. The paper manages to address the gap of online consistency of the nearest neighbour rule, and outline various interesting conditions for settings in which nearest neighbours rule is consistent. The paper is also quite well written.", "weaknesses": "One comment I have regarding the technical novelty is that the proof techniques in this paper are fairly standard across the literature on online learning and consistency of nearest neighbours. I mention this in case the authors would like to highlight something that is not actually a standard technique. This comment does not affect the score.\n\n1. It seems that the paper only proves results for the $1$-NN setting. See point 2 of the questions section.\n2. Section 6 seems to serve expository purposes. See point 4 of the questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading of the paper and for your thoughtful\ncomments. To address your comments/questions:\n\n0. On the technical contributions of this work: while we do owe a great deal to\n   prior work in online learning, nearest neighbor methods, and geometric\n   measure theory (see our references), we did also introduce a few new notions\n   and proof techniques:\n   \n   (a) Mutually labeling sets\n\n   (b) Approximations by essentially boundaryless functions\n\n   (c) Uniform absolute continuity and ergodic continuity\n\n   (d) Ergodic continuity of the nearest neighbor process\n\n   For example, (a) and (b) also lead to a new, simple proof of the classic\n   consistency result of 1-NN in the i.i.d. setting. The introduction of (c)\n   bridges two existing parts of online learning that seemed to be unaware of\n   each other (the smoothed online learning setting and the universal optimistic\n   online learning setting; see the related works section). And (d) establishes\n   a basic result about the behavior of the nearest neighbor process, which may\n   be of interest in its own right for nearest neighbor methods in general. And\n   of course, the main contribution on the consistency of the 1-NN rule in much\n   broader settings than previously known is also new.\n\n1. Dasgupta (2012) considered nearest neighbor rules under selective sampling.\n   In this setting, a stream of data $(X_n, Y_n)$ are drawn i.i.d. and presented\n   to the learner, but the true label is not automatically revealed. Rather, the\n   learner decides when to observe the accompanying label of an instance. Unlike\n   the standard 1-NN learner, the data in the selective sampler's memory is not\n   necessarily an i.i.d. snapshot of the world. On the other hand, the stream of\n   test instances are still drawn i.i.d. from a fixed underlying distribution,\n   so this is what we meant when we said that Dasgupta (2012) considered a\n   \"non-online setting where the train and test distributions differ\"\n   \n2. The easier result of consistency for the class $\\mathcal{F}_0$ of essentially\n   boundaryless functions extends easily to the k-NN rule. One just needs to\n   argue that eventually all the k nearest neighbors are contained in the same\n   mutually labeling set as the test instance. The k_n-NN rule seems a bit more\n   involved, and we don't have a proof for that. The harder part to extend is\n   our analysis of the nearest neighbor process to the k_n-nearest neighbors\n   process. That is certainly of interest, especially to your next question\n   about learning in the presence of noise.\n\n3. The problem is surprisingly subtle when there is noise. For the noisy\n   setting, we do have a preliminary consistency result for k_n-NN for uniformly\n   dominated processes with the constant label function on the unit interval.\n   One reason why noise may add a seemingly new challenge is that the adversary\n   could \"make patterns out of noise\". We're happy to say more about this, but\n   it does seem that the noisy setting is not at all an easy extension of the\n   realizable setting, requiring additional insight and techniques.\n\n4. The conjecture you gave also seemed very natural to us; we had tried to\n   further weaken the uniform domination condition. The conjecture turns out to\n   be false (if we understood \"mixing\" correctly). Blanchard (2022) constructs\n   \"mixing\" sequences such that 1-NN is inconsistent (more precisely, by\n   \"mixing\", we mean that the rate that $\\mathbb{X}$ hits any fixed measurable\n   set $A$ converges; Blanchard (2022) says that these sequences have \"convergent\n   relative frequencies\" or are CRF). \n   \n   Intuitively, uniform domination constrains how the sequence of instances is\n   generated, while ergodic domination (or the CRF condition) only constrains\n   how that sequence looks in retrospect. Loosely speaking, the CRF/ergodic\n   domination conditions are blind to the order in which the points came,\n   whereas the nearest neighbor process depends very much on that order. For\n   that reason, the more relaxed ergodic domination condition doesn't give us\n   enough control over the behavior of the nearest neighbor rule to prove\n   convergence.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ugso1c6YXa", "reviewer": "Reviewer_4b2W", "summary": "This paper studies the problem of non-uniform consistency of the nearest neighbor prediction rule when the instances are generated by a random process that has conditional marginals dominated by some underlying reference measure. In particular, it generalizes the well-known results of Cover and Hart (1967) for iid processes and the result of Kulkarni and Posner (1995) for arbitrary processes with strong assumptions on labeling functions. The paper shows that under the uniform dominance condition of the process, the NN rule is consistent for any measurable function, which is further extended to finite sample rates with additional assumptions on both the instance space and processes.", "questions": "See above.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I believe studying the consistency of the nearest neighbor prediction rule under a general random process is an important problem for understanding its limitations. This paper makes a significant step toward such a goal. From a philosophical perspective, this work is analogous to the recent line of work in beyond worst-case online learning in the infinite consistency paradigm. The paper also develops several original techniques, such as the control of the nearest neighbor process in Theorem 15, which may be of independent interest.\n\nOverall, I think this is an interesting paper and is suitable for publication at NeurIPS.", "weaknesses": "My main complaint about this paper is its writing style. The paper leans too much on geometric concepts (such as doubling metric spaces, length spaces, box-counting dimension, and Minkowski content), which, in my opinion, are not necessary to demonstrate the learning-theoretical insights and place an undue burden on the reviewers. Why not just focus on the Euclidean space in the main text and leave the generalizations for the appendix or a journal version?\n\nI have also the following specific comments:\n\n1. Can the authors comment on why all the main theorems assume uniform dominance rather than the more relaxed ergodic dominance? My understanding is that the only place where uniform dominance is used is in the Borel-Cantelli argument in the proof of Lemma D.4. Am I right?\n\n2. To be honest, I don't quite understand how the \"sequentially-constructed cover tree\" works. The sketch from lines 237-253 doesn't really help too much. Are the whole arguments merely to improve the $1/\\delta$ to $\\log(1/\\delta)$? Why can't one simply extend the argument in Example 17 using multiple indicators, if the goal is only consistency?\n\n3. I would recommend the authors move part of Section 7 to the appendix and put more effort in the main text on explaining the proof of Theorem 15.\n\n4. Can the authors comment on how the results from Blanchard (2022) compare to your results? Does the kC1NN rule proposed therein achieve consistency in your setting?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful reading of the paper and for your thoughtful\ncomments. To address your comments/questions:\n\n0. On the decision to present the results in more general metric measure space\n   setting over Euclidean space: the main tradeoff we were making was between\n   the benefits of a reader's familiarity with Euclidean space versus being able\n   to precisely disentangle which of the many nice properties of $(\\mathbb{R}^n,\n   \\ell_2, \\nu_\\mathrm{Lebesgue})$ are used to show consistency and each step\n   of the proof. Reconsidering, Section 7 would probably benefit from being\n   presented in the Euclidean setting rather than in the more abstract length\n   space; we can improve on this in the revisions.\n\n1. Ergodic domination by itself is not enough to achieve consistency. In fact,\n   Blanchard (2022), which you cite in Question 4, construct an ergodically\n   dominated stochastic process for which the 1-NN rules is not consistent. The\n   process they construct has \"convergent relative frequencies\" (CRF), which is\n   a stronger condition than being ergodically dominated (but weaker than being\n   uniformly dominated). To get the definition of CRF, replace in our definition\n   of ergodic domination the inequality \"$\\leq \\epsilon(\\nu(A))$\" by the\n   equality \"$= \\nu(A)$\".\n\n   Intuitively, uniform domination constrains how the sequence of instances is\n   generated, while ergodic domination only constrains how that sequence looks\n   in retrospect. Loosely speaking, the ergodic domination condition is blind to\n   the order in which the points came, whereas the nearest neighbor process\n   depends very much on that order. For that reason, the more relaxed ergodic\n   domination condition doesn't give us enough control over the behavior of the\n   nearest neighbor rule to prove convergence.\n   \n   Uniform domination is crucial for us in the step where we show that the\n   nearest neighbor process is ergodically dominated; it seems very difficult to\n   significantly relax the assumption here. We discuss this more in point 4c.\n\n   Lemma D.4 is a fairly unimportant in the overall picture; it allows us to\n   argue that it is enough to construct arguments on bounded metric spaces. The\n   error incurred by \"unbounded\" instances can be made arbitrarily small. \n\n2. We have clarified the exposition for Section 6. We removed the sketch you\n   mentioned; it was misleading because the point isn't to make the $1/\\delta$\n   to $\\log 1/\\delta$ improvement.\n\n3. Thanks for this comment; it makes a lot of sense to give Section 6 greater\n   focus.\n\n4. Our work relates to Blanchard (2022) in three ways: \n\n   (a) A direct way is through their negative result mentioned above: ergodic\n   domination is not sufficient to guarantee online consistency of 1-NN.\n\n   (b) These two works ask complementary but distinct questions. Blanchard\n   (2022) takes up a complexity-like concern about characterizing the \"minimal\"\n   conditions under which learning is possible. Earlier, Hanneke (2021)\n   introduced necessary conditions; Blanchard (2022) shows that they are also\n   sufficient. While 1-NN itself is not consistent under provably minimal\n   condition, a nearest-neighbor-like rule kC1NN is, which is the 1-NN rule with\n   the modification that an instance is discarded from memory once it has been\n   used k times to predict (the \"k-capped 1-NN rule\"). Our work takes up a more\n   algorithms-like concern, about what happens when the 1-NN rule is used under\n   settings that are not i.i.d., and how to study this.\n   \n   (c) Anecdotally, in the process of developing this research, we also\n   discovered a version of the kC1NN algorithm (at this point, we didn't know\n   about Blanchard's work). This was a natural algorithm to consider because it\n   allows us to sidestep the issue of bounding any persisting influence of \"hard\n   points\", since they are evicted from memory after k hits.\n   \n   Actually, the consistency of kC1NN for ergodically dominated processes is\n   fairly straightforward under the earlier machinery we've developed before\n   Section 6. The idea is not unlike Theorem 14, where we approximate the\n   underlying concept $\\eta$ by an $\\eta_0$ with negligible boundary. The key\n   (but not unique) difference arises when bounding the errors from instances\n   whose nearest neighbors fall in the disagreement region {$\\eta \\ne \\eta_0$};\n   type (b) mistakes in Theorem 14. For the kC1NN rule, the type (b) error rate\n   by the k-capped nearest neighbor process is at most:\n   \n   $k \\times \\textrm{rate that }$ {$\\eta \\ne \\eta_0$} $\\textrm{ is hit by } \\mathbb{X},$\n\n   which can be made as small as we like by Lemma 12 as long as the generating\n   process is ergodically dominated. In other words, if the generating process\n   is ergodically continuous at a rate of $\\epsilon(\\delta)$, then the k-capped\n   nearest neighbor process is also ergodically continuous with a slower rate of\n   $k\\cdot \\epsilon(\\delta)$. In this way, the k-capped nearest neighbor process\n   is \"better behaved\" than the nearest neighbor process. Caveat: this remained\n   a proof sketch and we never checked all steps.\n   \n   In some sense, however, this forgetful modification of 1-NN is somewhat\n   counter-intuitive in the realizable setting (assumed by both papers).\n   Forgetting old data points tends to make sense when the underlying concept\n   class is changing/drifting, but here, the learner receives ground-truth\n   labels that are correct for all time. Our result along with Blanchard (2022)\n   allows us to raise new questions: why should the learner throw away correct\n   data? More precisely, what are natural or realistic adversaries such that the\n   forgetful mechanism is required for consistency? Can we illuminate more\n   clearly how the forgetful mechanism allows the learner to hedge against these\n   adversaries?", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to all the reviewers for reading our paper and the considered feedback
and questions. 

All reviewers thought that we study a fundamental question in learning theory,
and that our results are significant: we show that the 1-nearest neighbor rule
achieves online consistency in settings far more general than previously known
(which had required either i.i.d. or large-margin assumptions). We also
developed new techniques and interesting intermediate results to do so.

Based on the feedback and questions, it seems that we should further clarify the
contributions of this work and the technical exposition, which we will do in
revisions. To describe our contributions, we should elaborate on how our work is
placed in broader context. Recently, the area of non-worst-case online learning
has made significant strides, addressing the need to understand learning in
non-i.i.d. scenarios (e.g. continual and lifelong learning); it is especially
important in settings where the standard worst-case analysis provides theory
that is too pessimistic to inform practice (e.g. "in the worst case, learning is
impossible"). Two independent strands have emerged (see Related Work):

(a) the smoothed online learning setting

(b) the optimistic universal learning setting

The former has focused on providing algorithms and convergence rates for
smoothed processes in parametric settings (e.g. finite VC dimension, etc.). Our
work complements this with results in the non-parametric setting. Furthermore,
we also consider a more general class of stochastic processes. As is often the
case, the techniques for the parametric and non-parametric settings look quite
different.

The latter has focused more on the complexity-like question of learnability and
has characterized more precisely what are the worst-case settings in which
learning is still possible. There, it was shown that these "theoretically
learnable processes" can still be too hard for the 1-NN learner. Concerning the
behavior of 1-NN in non-i.i.d. settings, our work significantly shrinks the gap
in understanding from the other direction to the uniformly dominated
setting, a much more general setting than the i.i.d. setting.

Our paper connects these two strands within a refined chain of online settings:

   i.i.d. < smoothed < uniformly dominated < ergodically dominated < theoretically learnable < worst-case

We've also developed new techniques for the study of nearest neighbor methods,
including the simple notion of mutually-labeling sets and their connection to
the class of essentially boundaryless functions. Moreover, our result on the
behavior of the nearest neighbor process may be of independent interest.

Many fundamental questions remain to be worked out in the area of non-worst case
online learning theory. A few examples, some pointed out by reviewers, come to
mind: How do we learn in the non-realizable setting? With bounded memory?
When/why are new algorithms required to learn in harder settings? When are new
analyses required? Is there a cost to using a learning algorithm that assumes a
more adversarial setting than necessary? We believe that the perspective from
nearest neighbors is a fruitful one due to the algorithmic simplicity of these
methods. This paper helps lay some foundation and language to pursue these
questions from that framework.

Meta-review: The reviewers agreed that this is a technically solid paper on an interesting problem, and all three recommended for acceptance. The reviewers (particularly XeYp) made a few suggestions, and I encourage the authors to seriously consider these when revising their paper.
Decision: Accept (poster)