Universal consistency and rates of convergence of multiclass prototype algorithms in metric spaces

We study universal consistency and convergence rates of simple nearest-neighbor prototype rules for the problem of multiclass classification in metric paces. We first show that a novel data-dependent partitioning rule, named Proto-NN, is universally consistent in any metric space that admits a universally consistent rule. Proto-NN is a significant simplification of OptiNet, a recently proposed compression-based algorithm that, to date, was the only algorithm known to be universally consistent in such a general setting. Practically, Proto-NN is simpler to implement and enjoys reduced computational complexity. We then proceed to study convergence rates of the excess error probability. We first obtain rates for the standard $k$-NN rule under a margin condition and a new generalized-Lipschitz condition. The latter is an extension of a recently proposed modified-Lipschitz condition from $\mathbb R^d$ to metric spaces. Similarly to the modified-Lipschitz condition, the new condition avoids any boundness assumptions on the data distribution. While obtaining rates for Proto-NN is left open, we show that a second prototype rule that hybridizes between $k$-NN and Proto-NN achieves the same rates as $k$-NN while enjoying similar computational advantages as Proto-NN. We conjecture however that, as $k$-NN, this hybrid rule is not consistent in general.


Introduction
Let (X , ρ) be a separable metric space, equipped with its Borel σ-field (Cover and Hart, 1967). Assume that the feature element X takes values in X and let its label Y take values in Y = {1, . . . , M }. The error probability of an arbitrary decision function g : X → Y is Denote by ν the unknown probability distribution of (X, Y ) and let P j (x) = P{Y = j | X = x}, j ∈ Y.
Then the Bayes decision, g * (x) = arg max j∈Y P j (x), minimizes the error probability. This optimal error is denoted by In the standard model of pattern recognition, we are given labeled samples, D n = {(X 1 , Y 1 ), . . . , (X n , Y n )}, which are n independent copies of (X, Y ). Based on D n , one can estimate the regression functions P j by P j,n , j ∈ Y, and the plug-in classification rule g n derived from P j,n is g n (x) = arg max j∈Y P j,n (x).
The classifier g n is weakly consistent for the distribution ν if lim n→∞ E{L(g n )} = L * .
The classifier g n is universally consistent in the metric space (X , ρ) if it is consistent for any distribution ν over the Borel σ-field. Following the pioneering work of Cover and Hart (1967) and Stone (1977) on nearestneighbor classification, Zhao (1987); Devroye et al. (1996); Györfi et al. (2006) showed that the k-nearest neighbor rule (k-NN) is universally strongly consistent in the Euclidean space (R d , · 2 ) provided that k → ∞ and k/n → 0 as n → ∞. Kernel-based and various partitioning rules were shown to be universally consistent in R d as well (Devroye et al., 1996). For more general (and, in particular, infinite-dimensional) metric spaces, Cérou and Guyader (2006); Forzani et al. (2012) characterized the consistency of the k-NN rule in terms of a Besicovitch-type condition. In particular, Cérou and Guyader (2006) showed that in the binary case, |Y| = 2, a necessary and sufficient condition for the k-NN classifier to be weakly consistent for ν is that for all sufficiently small ε > 0, lim r→0 + P 1 µ(S X,r ) S X,r |P j (z) − P j (X)|µ(dz) > ε = 0.
Here, S x,r = {z ∈ X : ρ(x, z) ≤ r} denotes the closed ball centered at x and having radius r and µ is the marginal distribution of X. Abraham et al. (2006) established the strong consistency of a generalized moving-window rule under the same condition. By Besicovitch's density theorem (Federer, 1969), in R d -and more generally in any finite-dimensional normed space -condition (1) holds for all distributions ν. However, in infinite-dimensional spaces this condition may be violated (Preiss, 1979(Preiss, , 1981. As such, the k-NN and the moving-window classifiers are not universally consistent in general separable metric spaces. This violation is not an isolated pathology, occurring, for example, in the commonly used separable Gaussian Hilbert spaces (Tišer, 2003). Leveraging the consistency of k-NN in finite dimensions, the filtering technique (i.e., taking the first d n coordinates in some basis representation for an appropriate d n ) was shown to be universally weakly consistent by . However, that technique is only applicable in Hilbert spaces, as opposed to more general metric spaces.
Up until recently, sufficient and necessary conditions on a metric space under which a universally consistent rule exists in it was an open problem. Building upon the results of Kontorovich and Weiss (2014); Kontorovich et al. (2017) it has been recently shown by Hanneke et al. (2019) that a compression-based prototype classification rule named OptiNet is universally strongly consistent in any separable metric space. Moreover, it was shown to be universally strongly consistent in any metric space that admits a universally consistent classifier -the first algorithm known to enjoy this property.
Arguably, OptiNet is a rather complex algorithm (see Section 2). The first main result of this paper (Corollary 2) distills the core arguments used to establish OptiNet's consistency and shows that a novel, much simpler classification rule is universally strongly consistent in any metric space that admits a universally consistent classifier. In addition, its consistency proof is much simpler than that of OptiNet and its implementation is trivial. As OptiNet, this algorithm, henceforth termed Proto-NN (and formally presented in Section 2), is a prototype algorithm and has the advantage of reduced computational complexity. Concerning some other prototype nearest-neighbor rules, see Devroye et al. (1996, §19.3).
Another important property of a classification rule is the rate at which the excess error probability E{L(g n )} − L * convergences to 0 as n → ∞. For any classification rule g n , this rate can be arbitrarily slow without further assumptions on the unknown data distribution (Devroye et al., 1996). So to obtain a non-trivial rate of convergence one typically assumes that ν belongs to a large class of distributions meeting some smoothness and tail conditions.
For the case X = R d , rates of convergence for several algorithms were obtained under a variety of conditions (Devroye et al., 1996;Györfi et al., 2006). A common assumption is that the regression functions are Hölder-continuous, that is, there are some C > 0 and 0 < β ≤ 1 such that ∀x, z ∈ X , (2) The case β = 1 is know as Lipschitz continuity. Denoting the support of µ by supp(µ) = {x ∈ X : µ(S x,r ) > 0, ∀r > 0}, it is well known (Györfi et al., 2006) that if supp(µ) is bounded and the regression function is Hölder-continuous, then, for |Y| = 2, the k-NN rule with k = n 2β 2β+d achieves the rate While this rate holds also for the more general problem of L 1 real-valued bounded regression, Mammen and Tsybakov (1999); Tsybakov (2004); Audibert and Tsybakov (2007) showed that for binary classification, faster rates can be achieved under an additional margin condition. Recently, Puchkin and Spokoiny (2020) generalized the margin condition to the multiclass setting.
Definition 1 Let P (1) (x) ≥ · · · ≥ P (M ) (x) be the ordered values of P 1 (x), . . . , P M (x). Then the margin condition means that there are some α > 0 and c * > 0 such that Assuming that the regression function is Hölder-continuous, that the margin condition is satisfied, and that the marginal distribution µ of X has a density that satisfies the so called strong density condition, Audibert and Tsybakov (2007); Kohler and Krzyzak (2007); Gadat et al. (2016) showed that for the binary case, the k-NN rule and several other plug-in estimators achieve the rate Moreover, this rate was shown to be minimax optimal, meaning that, over the class of all distributions meeting the aforementioned conditions, this rate is also a lower bound for any classification rule. See Samworth (2012); Blaschzyk and Steinwart (2018) and references therein for even faster rates under stronger conditions on the regression function. The strong density condition under which the rates in (4) are established requires the density function to be bounded away from zero over the support of µ; a highly restrictive condition that does not hold for many distributions of practical interest. Recently, it has been shown by Döring et al. (2017) that the same rates in (4) are obtained by replacing the strong density condition, together with the Hölder condition (2), with a combined smoothness and tail condition, named modified Lipschitz condition, given by Chaudhuri and Dasgupta (2014) considered the related condition that there are some γ > 0 and C * > 0 such that for all x in the support of µ, Here, S o x,r = {z ∈ X : ρ(x, z) < r} denotes the open ball centered at x. They showed that in the binary case, under condition (6) and the margin condition (3), the k-NN rule achieves Evidently, for X = R d , the rates in (4) are revisited by setting γ = β/d. More generally, condition (6) can be seen as a uniform Besicovitch condition and is a-priori applicable in any separable metric space. In this paper, we further abstract the modified Lipschitz conditions (5) and (6) and consider the following combined smoothness and tail condition.
Definition 2 For each j ∈ Y, the function P j satisfies the generalized Lipschitz condition if there is a monotonically increasing function h : In Section 3, we first obtain rates for the k-NN rule under the generalized Lipschitz condition and the margin condition in terms of the function h (Theorem 3). For the case we revisit the same rates as in (7). While obtaining rates for Proto-NN is left open, we proceed to derive rates for a second novel prototype rule that hybridizes between Proto-NN and k-NN (Theorem 4). This rule, which we call Proto-k-NN, allows a reduction in computational complexity by compressing the data into m = O(n/k) prototypes while enjoying the same rates as k-NN; see also Xue and Kpotufe (2018) for results in the same spirit.
On the generalized Lipschitz condition. Note that for condition (8) to be non-trivial, the rate at which h(s) → 0 as s → 0 should appropriately reflect the geometry of X and the class of distributions µ under consideration. Consider for example two distinct points x, z ∈ R d lying in a region where µ is uniformly distributed. Denoting the Lebesgue measure by λ and abbreviating its measure on any ball by λ(S x,r ) = v d · r d , one can verify that for any 0 < r ≪ ρ(x, z), applying the triangle inequality for ⌈ρ(x, z)/r⌉ times over a path from x to z, the generalized Lipschitz condition (8) implies that for some constant c > 0, Hence, to allow for non-constant regression functions, one needs h(λ(S x,r )) = O(r), or equivalently h(s) = O(s 1/d ), as in the modified Lipschitz condition (5). More generally, assuming that µ is absolutely continuous with respect to λ, the Radon-Nikodym theorem (Federer, 1969) asserts that µ has a density, namely, there exists a function D : such that for any measurable A ⊆ R d , So, in this case, condition (8) with This condition should be compared to the Hölder condition (2); see also Györfi (1981). Similarly, for a general separable metric space, one may assume that µ is accompanied by an increasing "small-ball probability" function ψ : R + → R + with lim r→0 ψ(r) = 0 and a function K : X → R + such that for µ-almost all x ∈ X , In this case, an appropriate choice would be

Condition (8) then becomes
As an example, consider a doubling measure µ 0 with supp(µ 0 ) = X (Heinonen, 2012;Rigot, 2018). Such a measure satisfies that there exists C = C(µ 0 ) ≥ 1 such that for any x and any radius r > 0, Assuming that µ 0 has no atoms, the doubling property (13) implies that there exists τ > 0 such that Since doubling measures satisfy a differentiation theorem similar to (10), a large class of distributions that satisfy (12) consists of all distributions µ that are absolutely continuous with respect to µ 0 . Here, K in (12) is again related to µ's density with respect to µ 0 . It is worth mentioning, however, that in infinite-dimensional spaces, doubling measures may not exist and a differentiation theorem may not hold; see Heinonen (2012); Rigot (2018).
In the field of non-parametric functional data analysis (Ferraty and Vieu, 2006;Burba et al., 2009;Baíllo et al., 2011;Ling and Vieu, 2018), where input data items are in the form of random functions, distributions µ accompanied by ψ in the form of (14) are said to have a fractal dimension τ ; see Pesin (1993); Bardet (1997) for concrete examples. Similarly to (7), a finite fractal dimension leads to rates of order n −ξ for an appropriate ξ = ξ(τ, α, β) > 0. However, in infinite-dimensional spaces, one typically encounters distributions of exponential type, where for some C > 0 and τ, τ ′ > 0, Such distributions include, for example, various diffusion and Gaussian processes; see Ferraty and Vieu (2006, §13) and references therein. In this case, non-parametric estimators suffer from extremely slow convergence rates of order log(n) −ξ , even for estimating the regression function at a fixed point x ∈ X (Ferraty and Vieu, 2006;Mas, 2012). One may overcome such slow rates by considering a semi-metric over X (where the condition ρ(x, y) = 0 ⇒ x = y is removed) instead of a metric, but coming up with an appropriate semi-metric can be a challenging task (Ferraty and Vieu, 2006). Lastly, we note that faster rates can be achieved in infinite-dimensional spaces, uniformly over the support of µ, in terms of covering numbers, assuming the support of µ is totally bounded (Kulkarni and Posner, 1995;Ferraty et al., 2010;Kudraszow and Vieu, 2013;Biau et al., 2010). Here we do not make such an assumption.

Universal consistency of Proto-NN
In this section we show that a simple prototype classification rule, which we call Proto-NN, is universally strongly consistent in any separable metric space. By the recent results of Hanneke et al. (2019), this implies that Proto-NN is in fact universally strongly consistent in any metric space that admits a universally consistent rule; see also Collins et al. (2020).
To simplify Proto-NN's analysis, we assume that in addition to the labeled sample D n , we also have an independent unlabeled sample X ′ m = {X ′ 1 , . . . , X ′ m } where the X ′ i 's are independent copies of X. Introduce the data-driven partition P m of X such that P m is a Voronoi partition with the nucleus set X ′ m , i.e., where tie breaking is done by indices, i.e., if X ′ i and X ′ j are equidistant from x, then X ′ i is declared "closer" if i < j. Proto-NN estimates the regression function P j over each cell by the piecewise constant functioñ such that 0/0 = 0 by definition. Proto-NN is then defined bỹ This rule is just the empirical majority vote over the labeled samples from D n that fell into the cell in which x resides, as determined by X ′ m . To establish Proto-NN's universal consistency, we first establish its consistency for the more general problem of L 1 real-valued bounded regression (Györfi et al., 2006). Formally, let the label Y be real-valued, and denote the corresponding regression function by Introduce the partitioning regression estimate: Theorem 1 If Y is bounded and m = m n → ∞ such that m n /n → 0, then the estimate f n is strongly consistent in L 1 , that is, for any distribution ν of (X, Y ), We conjecture that Theorem 1 can be generalized such that the strong consistency in L 1 holds for any distribution of (X, Y ) with E{|Y |} < ∞.
The following corollary establishes the universal consistency of Proto-NN.
Corollary 2 If m = m n → ∞ such that m n /n → 0, then the classification ruleg n is universally strongly consistent, that is, for any distribution of (X, Y ), lim n→∞ L(g n ) = L * a.s.
We conclude this section with a brief comparison of Proto-NN to the recently proposed OptiNet classifier of Hanneke et al. (2019), which, to date, was the only algorithm known to be universally consistent in any separable metric space. Denoting the instances in D n by X n = {X 1 , . . . , X n }, OptiNet first constructs several γ-nets of X n for different candidate values of γ > 0 (a γ-net of X n is any maximal set X(γ) ⊆ X n in which all interpoint distances are at least γ). Each γ-net serves as a nucleus set for a corresponding Voronoi partition of X . For each such partition, a prototype classifier is constructed by taking a majority-vote in each of its cells. Then an optimal γ * is selected among the different candidates by minimizing a compression-based generalization bound over γ. Alternatively, γ * can be chosen via a cross-validation procedure using a hold-out dataset. Hanneke et al. (2019) observed that a model selection procedure for choosing γ * cannot be readily avoided, since one cannot choose a-priori a determinstic sequence γ n for which OptiNet is consistent for all distributions. This is in contrast to Proto-NN, for which any m = m n → ∞ with m n /n → 0 will do. Of course, in practice, m should be chosen based on the data, as done with γ * .

Rates of convergence
In this section our focus lies on the rate at which the excess error probability E{L(g n )} − L * → 0.
We first derive rates for the k-NN rule under the margin condition (1) and the generalized Lipschitz condition (2) (Theorem 3). Obtaining convergence rates for the universally consistent Proto-NN classifier of Section 2 under these conditions (or any other condition mentioned in Section 1 for that matter) is currently an open research problem. Here, we instead derive rates for a second novel prototype rule, Proto-k-NN, that hybridizes between the Proto-NN and k-NN rules (Theorem 4). As shown below, Proto-k-NN allows a reduction in computational complexity by compressing the data into m = O(n/k) prototypes while enjoying the same rates as the k-NN rule.
We first make an additional simplifying assumption. For a fixed x ∈ X , let be the cumulative distribution function of ρ(x, X). In the sequel, we assume that H x (·) is continuous for each x. This assumption holds, for example, in the case that X = R d and X has a density. If H x (·) is continuous, then in the definition of nearest neighbors, tie happens with probability zero. In general, one can achieve that H x (·) is continuous by adding a randomized component to X: takeX = (X, U ) such that X and U are independent, U is uniformly distributed on [0, 1], and ρ((x, u), (X, U )) := ρ(x, X) + δ|u − U | for some small δ > 0. One can verify thatρ is indeed a metric.
X (n,k) (x) is the k-th nearest neighbor of x where tie breaking is done by indices. As discussed above, in this paper we assume that tie happens with probability zero. Choose an integer k less than n, then the k-nearest-neighbor estimate of P j is and the k-nearest-neighbor classification rule is Concerning the properties of the k-nearest-neighbor rule and the related literature see Devroye et al. (1996), Györfi et al. (2006), and Biau and Devroye (2015).
In the following theorem we bound the rate of convergence of the excess error probability E{L(g k,n )} − L * for the k-nearest-neighbor classification rule. In this way we extend the results of Kohler and Krzyzak (2007), Gadat et al. (2016), Döring et al. (2017) to the multiclass and to the metric space case. Notice that the paper by Biau et al. (2010) contains rate of convergence results for nearest neighbor regression estimate and Banach space valued features, which has implications for classification, too; cf. Chaudhuri and Dasgupta (2014).
Theorem 3 Assume that the distribution function H x (·) is continuous for each x. If the margin condition is satisfied with 0 < α and the generalized Lipschitz condition is met, then for k/ log n → ∞, In the case of X = R d and h(s) = s β/d as in (11), yields the order as in (4). For the two-class problem, Audibert and Tsybakov (2007, Theorem 3.5) showed that, under the strong density assumption and the margin condition with αβ ≤ d, (20) is the minimax optimal rate of convergence for the class of β-Hölder-continuous P j 's, that is, the order (20) is a lower bound for any classifier.
Rates for the Proto-k-NN rule. We now introduce a new prototype rule, termed Proto-k-NN, that hybridizes between k-NN and Proto-NN, and works as follows.
Similarly to Proto-NN (see Section 2), an unlabeled sample X ′ m serves as a nucleus set, inducing a Voronoi partition P m of X . Instead of taking a majority vote in each Voronoi cell, Proto-k-NN stores at each nucleus the majority vote among the k-nearest neighbors of that nucleus. Formally, let X ′ (m,1) (x) be the first nearest neighbor of x among X ′ m . We fix x ∈ X , and let X (n,k) (X ′ (m,1) (x)) be the k-th nearest neighbor of X ′ (m,1) (x) from the set X n and Y (n,k) (X ′ (m,1) (x)) stands for its label. The tie breaking is done by randomization. Again, in this section we assume that tie happens with probability 0. Choose an integer k less than n, then Proto-k-NN estimates P j (x) by the piecewise constant function and the corresponding prototype nearest-neighbor classification rule iŝ g n (x) = arg max j∈YP n,j (x).

Theorem 4 Assume that the distribution function H x (·) is continuous for each x. If the margin condition is satisfied with 0 < α and the generalized Lipschitz condition is met with
h that is concave, then for k/ log n → ∞, According to this theorem, the proper choice of m is proportional to n/k. For k as in (19), we obtain the same optimal rates as in (20). We conjecture however that, similarly to k-NN, this rule is not universally consistent in all separable metric spaces.

Proof of universal consistency
Proof of Theorem 1. Put Then, are called estimation errror and approximation error, respectively. Introduce the notations Concerning the estimation error, If L stands for a bound on |Y |, then |ϑ n (V )| ≤ Lµ n (V ) and The first term of the right hand side is a special case of the second one, therefore we bound only the tail distribution of the second term. Let σ(P m ) be the σ-algebra generated by P m . As in Biau and Györfi (2005), the equality |a − b| = 2(a − b) Thus, for any ε > 0, the Hoeffding inequality implies Therefore, m n /n → 0 together with the Borel-Cantelli lemma implies that and the consistency of the estimation error is proved. Concerning the approximation error, refer to Lemma A.1 in Hanneke et al. (2019) such that choose a Lipschitz function f * with a Lipschitz constant C and with a support contained in a sphere S such that Then, Recall that X ′ (m,1) (x) denotes the first nearest neighbor of x among X ′ m . For x, z ∈ V , ρ(x, z) ≤ ρ(x, X ′ (m,1) (x)) + ρ(X ′ (m,1) (x), z) = ρ(x, X ′ (m,1) (x)) + ρ(z, X ′ (m,1) (z)), where we applied, that V is a Voronoi cell and so for any x, z ∈ V , the nucleuses X ′ (m,1) (x) and X ′ (m,1) (z) are identical. Thus, Cover and Hart (1967) proved that, for a separable metric space, ρ(x, X ′ (m,1) (x)) → 0 a.s. as m → ∞, for µ-almost all x, cf. Lemma 6.1 in Györfi et al. (2006). Therefore, the dominated convergence yields concluding the proof of Theorem 1.

Proofs of convergence rates
The rates of convergence for the k-NN and Proto-k-NN classifiers of Section 3 are derived using the following decomposition of the excess error probability.
Lemma 5 Let g n be a plug-in rule with estimates P n,j of P j as in Section 1. Abbreviating Below, we bound J n,j,l for each algorithm separately.
Proof of Lemma 5. For any decision function g, The relation Thus, Taking expectation and integrating with respect to µ concludes the proof of Lemma 5.
For each j and l, we show that Concerning the approximation error J n,j,l , we follow the line of proof of Lemma 2 in Döring et al. (2017). The generalized Lipschitz condition implies that h(µ(S x,ρ(x,X (n,i) (x)) )) ≤ h(µ(S x,ρ(x,X (n,k) (x)) )).