Rates of Convergence for Large-scale Nearest Neighbor Classification

Guang Cheng; Jiexin Duan; Xingye Qiao

REVIEW 2 major objections 4 minor 48 references

Rates of Convergence for Large-scale Nearest Neighbor Classification

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Dividing a large data set across machines and majority-voting local kNN predictions yields the same optimal error rate as the oracle full-data kNN.

desk verdict A clean rate analysis for split-and-vote kNN whose central theorem holds, but the claimed Hölder minimax optimality rests on an unjustified bridge. read the letter →

arxiv 1909.01464 v2 pith:X7YND4NT submitted 2019-09-03 stat.ML cs.LGmath.STstat.TH

Xingye Qiao , Jiexin Duan , Guang Cheng This is my paper · ORCID

classification stat.MLcs.LGmath.STstat.TH MSC 62H3062G0868T05

keywords nearestneighborclassificationdivideandconquermajorityvotingdistributedlearningexcessriskinstabilitymarginconditionminimaxconvergencerate

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether a practical distributed scheme—split the training data into $s$ pieces, run $k$-nearest-neighbor on each piece, and combine the local predictions by majority vote—loses any statistical accuracy compared with running kNN on the full data. Its answer is no, asymptotically. Under a smoothness condition on the regression function $\eta$ that measures variation in probability mass rather than distance, plus the standard $\beta$-margin condition, the big Nearest Neighbor (bigNN) classifier attains expected excess risk at most $C_0 N^{-\alpha(\beta+1)/(2\alpha+1)}$ with $N=ns$ total samples, exactly the rate of the oracle kNN classifier, and the same holds for classification instability. These rates are minimax optimal, so memory, communication, and privacy constraints cost no convergence rate in the worst case. The paper also characterizes how the local neighbor count $k$ must scale with both $n$ and $s$, and adds a denoising acceleration step that cuts prediction time at a controlled cost in accuracy.

What carries the argument

The load-bearing object is the $(\alpha,L)$-smoothness condition $|\eta(x)-\eta(x')| \le L\,\mu(B(x,\rho(x,x')))^{\alpha}$, which measures how fast the class probability changes as a function of the probability mass of a ball rather than its radius. Combined with the $\beta$-margin condition $P(|\eta(X)-1/2|\le t)\le Ct^{\beta}$, this controls the effective boundary, the set where kNN can disagree with the Bayes classifier. The proof bounds the probability that any single local classifier deviates from the Bayes label by checking whether the query point is near the boundary, whether the $k$-th neighbor is farther than the radius $r_p(x)$, and whether the local label average deviates from $\eta$; a Chernoff concentration inequality then controls the majority-vote ensemble, and the choice of $k$ balances the boundary term against the concentration terms. For the denoised variant, the additional machinery is a nearest-neighbor distance lemma in a subsample of size $m$, used together with VC-dimension and the margin condition.

What would settle it

Run the bigNN classifier on a synthetic distribution with a point mass exactly at the Bayes boundary and smooth $\eta$ elsewhere, choosing $k$ as in Theorem 1. If the measured excess risk decays slower than $N^{-\alpha(\beta+1)/(2\alpha+1)}$, the failing premise is the $(\alpha,L)$-smoothness condition at the atom; equivalently, check the inequality $|\eta(x)-\eta(x')| \le L\,\mu(B(x,\rho(x,x'))){}^{\alpha}$ at radii around $p=2k/n$ near the boundary.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: choosing $k = k_0 n^{2\alpha/(2\alpha+1)} s^{-1/(2\alpha+1)}$, the expected excess risk of the bigNN classifier satisfies $\mathrm{E}_N R_{n,k,s} - R^* \le C_0 N^{-\alpha(\beta+1)/(2\alpha+1)}$ under $(\alpha,L)$-smoothness of $\eta$ and the $\beta$-margin condition. This matches the oracle kNN rate and is sharp by known minimax bounds. Theorem 2 gives the analogous bound $N^{-\alpha\beta/(2\alpha+1)}$ for classification instability. A notable structural finding is that the optimal local $k$ is smaller than the oracle $k$ for a subsample of size $n$: individual local classifiers are deliberately suboptimal, yet majority voting across $s$ pieces restores a globally optimal classifier. This works only when $s$ does not grow too fast, specifically $s$ must stay below order $N^{2\alpha/(2\alpha+1)}$. Theorem 3 bounds the additional regret of the denoised, pre-trained variant by $(d_{\text{vc}}\log(m/\delta)/(m C_d))^{\alpha_H(\beta+1)/d'}$, so the acceleration is asymptotically negligible when the prediction-stage subsample size $m$ is large enough.

Load-bearing premise

The $(\alpha,L)$-smoothness condition on $\eta$ must hold for all balls down to the scale of the $k$ nearest neighbors, including right at the decision boundary; if the marginal distribution has atoms or regions where its density vanishes, the condition can fail even when $\eta$ is smooth in the usual Euclidean sense, and the claimed rate does not follow.

Editorial extensions

If this is right

bigNN achieves the same minimax-optimal excess-risk rate as the oracle full-data kNN, so distributed storage and communication constraints do not degrade the asymptotic classification accuracy.
The optimal local neighbor count must be $k = k_0 n^{2\alpha/(2\alpha+1)} s^{-1/(2\alpha+1)}$, not the oracle-optimal $n^{2\alpha/(2\alpha+1)}$; using the oracle choice locally would be suboptimal for the ensemble.
The number of splits $s$ has an upper limit: the stated rate requires $s$ to grow slower than $N^{2\alpha/(2\alpha+1)}$, and simulations show performance deteriorating when $s$ grows too fast, so a sharp bound on $\gamma$ with $s=N^{\gamma}$ is left as future work.
Classification instability of bigNN also decays at the oracle rate $N^{-\alpha\beta/(2\alpha+1)}$, meaning the distributed ensemble is as stable under resampling as full-data kNN.
Pre-training with bigNN and then predicting by 1-NN on a subsample of size $m$ adds only a controlled error term, so prediction time can be reduced to near 1-NN cost without losing the optimal rate when $m$ is sufficiently large.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same majority-voting argument likely extends to weighted nearest-neighbor base classifiers, in which case the ensemble could inherit not only the optimal rate but also the optimal constant from the weighted oracle.
For data whose feature distribution has atoms, a singular component, or density vanishing near the decision boundary, the $(\alpha,L)$-smoothness condition is the real bottleneck; practitioners should check whether $\mu(B(x,\rho))$ behaves like a power of the radius before relying on the stated rate.
The upper bound on $s$ gives a practical rule of thumb: keep the splitting exponent $\gamma$ below $2\alpha/(2\alpha+1)$; when $\alpha$ is unknown, tuning the number of partitions by cross-validation may avoid the bias regime documented in the paper's simulations.
Because the denoising error depends on the intrinsic dimension $d'$, data lying on a low-dimensional manifold could allow very small prediction-stage subsamples $m$ while preserving the optimal rate, making the acceleration even more favorable than the ambient-dimension calculation suggests.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Work you should know about: this is the first careful rate analysis of the simplest divide-and-conquer kNN—split the data, run kNN on each piece, majority vote. Theorem 1 proves that under the Chaudhuri–Dasgupta (α,L)-smoothness condition on η and the β-margin condition, with k = k0 n^{2α/(2α+1)} s^{-1/(2α+1)}, the excess risk is O(N^{-α(1+β)/(2α+1)}), the same as the oracle full-data kNN. Theorem 2 gives the matching CIS rate. The proofs are in the supplement and are internally consistent; the Chernoff bound over the s independent local classifiers is the right tool, and the k-scaling law is a genuine insight.

Where the paper is genuinely new: the method is old (they admit it), and bagged/stabilized NN already hit these rates, but nobody had shown the distributed majority-vote version attains them. That is a useful gap to close, and the analysis is clean enough to be teachable. The citation pattern is honest, and the CIS result is proved independently rather than borrowed.

Now the soft spots. The main one is equation (1). The paper claims Hölder continuity with exponent α_H implies (α,L)-smoothness with α = α_H/d. That is only true with a uniform lower bound on the density of μ (e.g., μ(B(x,r)) ≥ c r^d). Without it, μ(B(x,r)) can be o(r^d), and a Hölder η need not be (α,L)-smooth at the scales the proof uses. This matters because the minimax optimality claim is made by comparing to Audibert–Tsybakov lower bounds for Hölder classes; the bridge (1) is what justifies the comparison. The theorem itself stands under the stated (α,L)-smoothness, but the 'cannot be improved' claim over Hölder classes is not established. This is fixable—add a density lower bound to the comparison or prove a direct lower bound for the smooth-measure class—but it is not just cosmetics.

Second, Theorem 3's denoising bound is sketched. The proof passes through a choice of δ̃ and a condition like (8δ̃)^{s/2} < δ, but the relationship between n, m, s, and the constants is not spelled out. It reads plausible, not verified. The simulations are suggestive but not decisive: no code, no error bars, and one hand-tuned constant (k_o^* = 1.351284) in Simulation 3.

Bottom line: this is a solid, honest paper that deserves a serious referee. The central theorem is correct under its assumptions; the issue is the scope of the optimality claim. I would send it out and ask the authors to fix (1) or qualify the Hölder comparison, and to tighten the proof of Theorem 3.

Recommendation: engage with it. It is worth citing for the bigNN rate, with a note on the density condition.

Referee Report

2 major / 4 minor

Summary. The paper proposes bigNN, a divide-and-conquer k-nearest-neighbor classifier in which the training set is split into s subsets, kNN is run on each subset, and the local predictions are combined by majority voting. Under an (α,L)-smoothness condition on the regression function η with respect to the marginal measure μ and a β-margin condition, Theorem 1 bounds the expected excess risk by O(N^{-α(β+1)/(2α+1)}), and Theorem 2 bounds the classification instability by O(N^{-αβ/(2α+1)}). Theorem 3 adds a denoising pre-training step and bounds its additional regret. The paper compares these rates with oracle kNN and with Hölder-based minimax rates, and presents simulations and benchmark experiments.

Significance. If the main claims held as stated, the paper would be a useful contribution: it would show that a simple, communication-friendly divide-and-conquer kNN attains the same rate as the oracle kNN while enjoying a large speedup. The proofs of Theorems 1 and 2 in the supplement are transparent and internally consistent under the stated μ-smoothness assumption, and the identification of the correct scaling k ∝ n^{2α/(2α+1)} s^{-1/(2α+1)} is a genuine insight. However, the paper's headline optimality claim depends on a Hölder-to-μ-smoothness implication that is not justified as stated, and the proof of the denoising theorem has a gap. These issues affect the central claims and require revision.

major comments (2)

[Section 2, Eq. (1)] The assertion that αH-Hölder continuity implies (α,L)-smoothness with α = αH/d is false without a uniform lower bound on the measure, e.g. μ(B(x,r)) ≥ c r^d. When μ has atoms, a singular component, or a density that vanishes on part of the support, μ(B(x,r)) can be o(r^d), so a Euclidean-Hölder η can violate the μ-smoothness inequality precisely at the local kNN scale p = 2k/n used in Supplement Lemma 1. Consequently, the rate conversions in Section 3 to N^{-αH(β+1)/(2αH+d)} and the statements that the bigNN rate is sharp and 'cannot be improved' are not established under the stated assumptions. The authors should either impose a density lower bound when making Hölder comparisons, or prove a matching lower bound directly under the (α,L)-smoothness and margin assumptions.
[Supplement, proof of Theorem 3] The step 'Choose \tildeδ so that \tildeφ < φ' is not always possible. Since \tildeφ = C(d_vc log(2n/\tildeδ)/(n C_d))^{αH/(2αH+d')} increases as \tildeδ decreases, its smallest value over \tildeδ ∈ (0,1) is attained at \tildeδ = 1. If φ is smaller than that minimum, no choice of \tildeδ satisfies \tildeφ < φ. This happens, for example, when m grows faster than n^{d'/(2αH+d')} (up to logarithmic factors). The theorem as stated therefore needs an explicit relation linking m, n and the constants, or a different argument for the denoising error.

minor comments (4)

[Section 3, Theorem 1] The statement 'Set k = k0 n^{2α/(2α+1)} s^{-1/(2α+1)} → ∞' is only meaningful when s grows slower than N^{2α/(2α+1)}; this condition is mentioned informally later but should be stated in the theorem.
[Section 4] In the sentence 'as long as the number of total subsamples s is no larger than N^{2αH/(1αH+d)}', the denominator appears to be a typo for 2αH+d; please correct and check that the matching with N^{2α/(2α+1)} is stated accurately.
[Supplement, proof of Theorem S.1] The expression 'δ4/s/4' is ambiguous; it should be written as δ^{4/s}/4 or with explicit parentheses.
[Section 5, Simulation 1] The paper reports correlations between fitted and observed log-regret values but not the estimated log(N) coefficients; reporting the slopes with standard errors would more directly verify the claimed exponents.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction found in the derivation chain; only a minor, non-load-bearing self-citation for the CIS optimality benchmark.

full rationale

Theorem 1's excess-risk bound is derived from first principles: Lemma 1 in the supplement bounds the pointwise regret under the (alpha,L)-smoothness and margin assumptions, and the final balancing step chooses k = k0 n^{2alpha/(2alpha+1)} s^{-1/(2alpha+1)} to balance the terms max[2L(2k/n)^alpha, (2(2+beta)/(ks))^{1/2}]^{1+beta}; k is solved from the proof, not fitted to data. The bigNN majority-vote argument in Theorem S.1 is an independent application of Chernoff bounds to the local base classifiers, not a restatement of the oracle rate. Comparisons with Chaudhuri-Dasgupta [9] and Audibert-Tsybakov [3] are external benchmarks. The only self-citation is [41] (Sun, Qiao, Cheng), used to state the previously known oracle CIS rate; the bigNN CIS upper bound in Theorem 2 is proved separately in the supplement, so this citation is not load-bearing. The transition formula alpha = alpha_H / d in equation (1) is a correctness or scope concern rather than a circularity: without a lower bound on mu(B(x,r)), Euclidean Holder continuity need not imply the (alpha,L)-smoothness inequality at the kNN ball radii, but this is an unproved implication about the assumptions, not an input-output identity. The admitted future work on proving a sharp upper bound on gamma is a completeness limitation, not a circular step. No fitted parameter is renamed as a prediction, and no theorem in the paper reduces by construction to its own inputs.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central theorems rest on standard smoothness and margin conditions, plus bounded-density-type measure regularity implicit in the (alpha,L)-smoothness definition. No new entities are introduced. The only hand-tuned constant appears in Simulation 3 and does not affect the theoretical results.

free parameters (2)

k0 = unspecified positive constant
Multiplier in the theoretical choice k = k0 n^{2alpha/(2alpha+1)} s^{-1/(2alpha+1)}. The theorems hold for any fixed k0 > 0; the rate does not depend on its value, so it is not a fitted parameter in the theory.
k0* = 1.351284
Hand-tuned local-neighbor multiplier used only in Simulation 3 to choose k = ceil(k0* K / s). The paper states it 'works well in this example'; it is not part of the main theoretical claim.

assumptions (5)

domain assumption The regression function eta is (alpha,L)-smooth: |eta(x)-eta(x')| <= L mu(B(x, rho(x,x')))^alpha for all x, x'.
Stated in Section 2 and used in Lemma 1 and Theorem 1 to bound the bias of local kNN.
domain assumption beta-margin condition: P(|eta(X)-1/2| <= t) <= C t^beta for all t > 0.
Stated in Section 2 and used to convert pointwise regret bounds into excess-risk rates.
standard math mu is a Borel regular probability measure on a separable metric space.
Background measure-theoretic framework, stated in Section 2.
domain assumption For Theorem 3, mu(B(x,r)) >= C_d r^{d'} for all x, r (intrinsic dimension lower bound), eta is alpha_H-Hoelder continuous, and the VC dimension d_vc is finite.
Additional conditions in Section 4 for the denoising acceleration bound.
standard math Chernoff, union bounds, and concentration inequalities for binomial and VC classes.
Used in Theorem S.1 and the proof of Theorem 3 in the supplement.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Rates of Convergence for Large-scale Nearest Neighbor Classification." pith.science (2026). https://pith.science/paper/X7YND4NT

@misc{pith2026190901464,
  author       = {Pith},
  title        = {Pith review of: Rates of Convergence for Large-scale Nearest Neighbor Classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X7YND4NT}},
  note         = {Machine review of arXiv:1909.01464}
}

abstract

Nearest neighbor is a popular class of classification methods with many desirable properties. For a large data set which cannot be loaded into the memory of a single machine due to computation, communication, privacy, or ownership limitations, we consider the divide and conquer scheme: the entire data set is divided into small subsamples, on which nearest neighbor predictions are made, and then a final decision is reached by aggregating the predictions on subsamples by majority voting. We name this method the big Nearest Neighbor (bigNN) classifier, and provide its rates of convergence under minimal assumptions, in terms of both the excess risk and the classification instability, which are proven to be the same rates as the oracle nearest neighbor classifier and cannot be improved. To significantly reduce the prediction time that is required for achieving the optimal rate, we also consider the pre-training acceleration technique applied to the bigNN method, with proven convergence rate. We find that in the distributed setting, the optimal choice of the neighbor $k$ should scale with both the total sample size and the number of partitions, and there is a theoretical upper limit for the latter. Numerical studies have verified the theoretical findings.

Figures

Figures reproduced from arXiv: 1909.01464 by the authors.

**Figure 2.** Scatter plots of the fitted and observed regret and CIS values. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Regret and CIS for bigNN and oracle kNN (γ = 0) for k = 5 fixed. Different curves represent different N. The results are shown in Figures 3. Both lines linearly decay in γ (both plots are on the log scale for the y-axis). We note that the expected slopes in these two plots should be −(1 + β)/2 × log(N) and −β/2 × log(N) respectively, which is verified by the figures, where larger N means steeper lines. Simulation 3:… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Regret and prediction time trade-off for denoised bigNN and bigNN (black diamonds). [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages

[1]

Optimizing parallel algorithms for all pairs similarity search,

Alabduljalil, M. A., Tang, X., and Yang, T. (2013), “Optimizing parallel algorithms for all pairs similarity search,” in Proceedings of the sixth ACM international conference on Web search and data mining, ACM, pp. 203–212

work page 2013
[2]

Parallel cosine nearest neighbor graph construction,

Anastasiu, D. C. and Karypis, G. (2017), “Parallel cosine nearest neighbor graph construction,” Journal of Parallel and Distributed Computing

work page 2017
[3]

Fast learning rates for plug-in classiﬁers,

Audibert, J.-Y . and Tsybakov, A. B. (2007), “Fast learning rates for plug-in classiﬁers,”Ann. Statist., 35, 608–633. 9

work page 2007
[4]

Searching for exotic particles in high-energy physics with deep learning,

Baldi, P., Sadowski, P., and Whiteson, D. (2014), “Searching for exotic particles in high-energy physics with deep learning,”Nature communications, 5, 4308

work page 2014
[5]

Distributed Estimation and Inference with Statistical Guarantees

Battey, H., Fan, J., Liu, H., Lu, J., and Zhu, Z. (2015), “Distributed estimation and inference with statistical guarantees,”arXiv preprint arXiv:1509.05457

work page Pith review arXiv 2015
[6]

Multidimensional binary search trees used for associative searching,

Bentley, J. L. (1975), “Multidimensional binary search trees used for associative searching,” Communications of the ACM, 18, 509–517

work page 1975
[7]

Bagging predictors,

Breiman, L. (1996), “Bagging predictors,” Machine learning, 24, 123–140

work page 1996
[8]

Accurate occupancy detection of an ofﬁce room from light, temperature, humidity and CO2 measurements using statistical learning models,

Candanedo, L. M. and Feldheim, V . (2016), “Accurate occupancy detection of an ofﬁce room from light, temperature, humidity and CO2 measurements using statistical learning models,” Energy and Buildings, 112, 28–39

work page 2016

Show all 48 references

[9]

Rates of convergence for nearest neighbor classiﬁca- tion,

Chaudhuri, K. and Dasgupta, S. (2014), “Rates of convergence for nearest neighbor classiﬁca- tion,” inAdvances in Neural Information Processing Systems, pp. 3437–3445

2014
[10]

Learning ensembles from bites: A scalable and accurate approach,

Chawla, N. V ., Hall, L. O., Bowyer, K. W., and Kegelmeyer, W. P. (2004), “Learning ensembles from bites: A scalable and accurate approach,” Journal of Machine Learning Research , 5, 421–451

2004
[11]

A split-and-conquer approach for analysis of extraordinarily large data,

Chen, X. and Xie, M.-g. (2014), “A split-and-conquer approach for analysis of extraordinarily large data,”Statistica Sinica, 1655–1684

2014
[12]

Nearest neighbor pattern classiﬁcation,

Cover, T. and Hart, P. (1967), “Nearest neighbor pattern classiﬁcation,”IEEE transactions on information theory, 13, 21–27

1967
[13]

Rates of convergence for nearest neighbor procedures,

Cover, T. M. (1968), “Rates of convergence for nearest neighbor procedures,” inProceedings of the Hawaii International Conference on Systems Sciences, pp. 413–415

1968
[14]

Randomized partition trees for exact nearest neighbor search,

Dasgupta, S. and Sinha, K. (2013), “Randomized partition trees for exact nearest neighbor search,” inConference on Learning Theory, pp. 317–337

2013
[15]

On the strong universal consis- tency of nearest neighbor regression function estimates,

Devroye, L., Gyorﬁ, L., Krzyzak, A., and Lugosi, G. (1994), “On the strong universal consis- tency of nearest neighbor regression function estimates,”The Annals of Statistics, 1371–1385

1994
[16]

A comparison of dynamic reposing and tangent distance for drug activity prediction,

Dietterich, T. G., Jain, A. N., Lathrop, R. H., and Lozano-Perez, T. (1994), “A comparison of dynamic reposing and tangent distance for drug activity prediction,” in Advances in Neural Information Processing Systems, pp. 216–223

1994
[17]

Solving the multiple instance problem with axis-parallel rectangles,

Dietterich, T. G., Lathrop, R. H., and Lozano-Pérez, T. (1997), “Solving the multiple instance problem with axis-parallel rectangles,”Artiﬁcial intelligence, 89, 31–71

1997
[18]

Distributed Estimation of Principal Eigenspaces,

Fan, J., Wang, D., Wang, K., and Zhu, Z. (2017), “Distributed Estimation of Principal Eigenspaces,”arXiv preprint arXiv:1702.06488

2017 arXiv
[19]

Discriminatory analysis-nonparametric discrimination: consistency properties,

Fix, E. and Hodges Jr, J. L. (1951), “Discriminatory analysis-nonparametric discrimination: consistency properties,” Tech. rep., California Univ Berkeley

1951
[20]

Distribution-free exponential error bound for nearest neighbor pattern classiﬁ- cation,

Fritz, J. (1975), “Distribution-free exponential error bound for nearest neighbor pattern classiﬁ- cation,”IEEE Transactions on Information Theory, 21, 552–557

1975
[21]

Efﬁcient classiﬁcation for metric data,

Gottlieb, L.-A., Kontorovich, A., and Krauthgamer, R. (2014), “Efﬁcient classiﬁcation for metric data,”IEEE Transactions on Information Theory, 60, 5750–5759

2014
[22]

Result analysis of the NIPS 2003 feature selection challenge,

Guyon, I., Gunn, S., Ben-Hur, A., and Dror, G. (2005), “Result analysis of the NIPS 2003 feature selection challenge,” inAdvances in neural information processing systems, pp. 545–552

2005
[23]

The rate of convergence of k_n-NN regression estimates and classiﬁcation rules (Corresp.),

Gyorﬁ, L. (1981), “The rate of convergence of k_n-NN regression estimates and classiﬁcation rules (Corresp.),”IEEE Transactions on Information Theory, 27, 362–364

1981
[24]

Choice of neighbor order in nearest-neighbor classiﬁcation,

Hall, P., Park, B. U., and Samworth, R. J. (2008), “Choice of neighbor order in nearest-neighbor classiﬁcation,” The Annals of Statistics, 2135–2152. 10

2008
[25]

Properties of bagged nearest neighbour classiﬁers,

Hall, P. and Samworth, R. J. (2005), “Properties of bagged nearest neighbour classiﬁers,” Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67, 363–379

2005
[26]

Approximate nearest neighbors: towards removing the curse of dimensionality,

Indyk, P. and Motwani, R. (1998), “Approximate nearest neighbors: towards removing the curse of dimensionality,” inProceedings of the thirtieth annual ACM symposium on Theory of computing, ACM, pp. 604–613

1998
[27]

On the rate of convergence of local averaging plug-in classiﬁcation rules under a margin condition,

Kohler, M. and Krzyzak, A. (2007), “On the rate of convergence of local averaging plug-in classiﬁcation rules under a margin condition,” IEEE transactions on information theory, 53, 1735–1742

2007
[28]

Nearest-neighbor sample compression: Efﬁciency, consistency, inﬁnite dimensions,

Kontorovich, A., Sabato, S., and Weiss, R. (2017), “Nearest-neighbor sample compression: Efﬁciency, consistency, inﬁnite dimensions,” in Advances in Neural Information Processing Systems, pp. 1573–1583

2017
[29]

A Bayes consistent 1-NN classiﬁer,

Kontorovich, A. and Weiss, R. (2015), “A Bayes consistent 1-NN classiﬁer,” in Artiﬁcial Intelligence and Statistics, pp. 480–488

2015
[30]

Time-accuracy tradeoffs in kernel prediction: controlling prediction quality,

Kpotufe, S. and Verma, N. (2017), “Time-accuracy tradeoffs in kernel prediction: controlling prediction quality,”The Journal of Machine Learning Research, 18, 1443–1471

2017
[31]

Rates of convergence of nearest neighbor estimation under arbitrary sampling,

Kulkarni, S. R. and Posner, S. E. (1995), “Rates of convergence of nearest neighbor estimation under arbitrary sampling,”IEEE Transactions on Information Theory, 41, 1028–1039

1995
[32]

Communication-efﬁcient Sparse Regres- sion,

Lee, J. D., Liu, Q., Sun, Y ., and Taylor, J. E. (2017), “Communication-efﬁcient Sparse Regres- sion,”Journal of Machine Learning Research, 18, 1–30

2017
[33]

Uci machine learning repository. university of california, irvine, school of information and computer sciences,

Lichman, M. (2013), “Uci machine learning repository. university of california, irvine, school of information and computer sciences,”

2013
[34]

Fifty years of pulsar candidate selection: from simple ﬁlters to a new principled real-time classiﬁcation approach,

Lyon, R., Stappers, B., Cooper, S., Brooke, J., and Knowles, J. (2016), “Fifty years of pulsar candidate selection: from simple ﬁlters to a new principled real-time classiﬁcation approach,” Monthly Notices of the Royal Astronomical Society, 459, 1104–1123

2016
[35]

Smooth discrimination analysis,

Mammen, E., Tsybakov, A. B., et al. (1999), “Smooth discrimination analysis,”The Annals of Statistics, 27, 1808–1829

1999
[36]

Scalable nearest neighbor algorithms for high dimensional data,

Muja, M. and Lowe, D. G. (2014), “Scalable nearest neighbor algorithms for high dimensional data,”IEEE Transactions on Pattern Analysis and Machine Intelligence, 36, 2227–2240

2014
[37]

Optimal weighted nearest neighbour classiﬁers,

Samworth, R. J. (2012), “Optimal weighted nearest neighbour classiﬁers,” The Annals of Statistics, 40, 2733–2763

2012
[38]

Computational limits of a distributed algorithm for smoothing spline,

Shang, Z. and Cheng, G. (2017), “Computational limits of a distributed algorithm for smoothing spline,”The Journal of Machine Learning Research, 18, 3809–3845

2017
[39]

Locality-sensitive hashing for ﬁnding nearest neighbors [lecture notes],

Slaney, M. and Casey, M. (2008), “Locality-sensitive hashing for ﬁnding nearest neighbors [lecture notes],”IEEE Signal processing magazine, 25, 128–131

2008
[40]

Distribution inequalities for the binomial law,

Slud, E. V . (1977), “Distribution inequalities for the binomial law,”The Annals of Probability, 404–412

1977
[41]

Stabilized Nearest Neighbor Classiﬁer and its Statistical Properties,

Sun, W. W., Qiao, X., and Cheng, G. (2016), “Stabilized Nearest Neighbor Classiﬁer and its Statistical Properties,”Journal of the American Statistical Association, 111, 1254–1265

2016
[42]

Optimal aggregation of classiﬁers in statistical learning,

Tsybakov, A. B. (2004), “Optimal aggregation of classiﬁers in statistical learning,”Annals of Statistics, 135–166

2004
[43]

On the Uniform Convergence of Relative Fre- quencies of Events to Their Probabilities,

Vapnik, V . and Chervonenkis, A. Y . (1971), “On the Uniform Convergence of Relative Fre- quencies of Events to Their Probabilities,” Theory of Probability and its Applications , 16, 264

1971
[44]

Convergence of the nearest neighbor rule,

Wagner, T. (1971), “Convergence of the nearest neighbor rule,”IEEE Transactions on Informa- tion Theory, 17, 566–571. 11

1971
[45]

Achieving the time of 1-NN, but the accuracy of k-NN,

Xue, L. and Kpotufe, S. (2018), “Achieving the time of 1-NN, but the accuracy of k-NN,” in Proceedings of the Twenty-First International Conference on Artiﬁcial Intelligence and Statistics, eds. Storkey, A. and Perez-Cruz, F., Playa Blanca, Lanzarote, Canary Islands: PMLR, vol...

2018
[46]

The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients,

Yeh, I.-C. and Lien, C.-h. (2009), “The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients,”Expert Systems with Applications, 36, 2473–2480

2009
[47]

Divide and conquer kernel ridge regression,

Zhang, Y ., Duchi, J., and Wainwright, M. (2013), “Divide and conquer kernel ridge regression,” in Conference on Learning Theory, pp. 592–617

2013
[48]

A partially linear framework for massive heteroge- neous data,

Zhao, T., Cheng, G., Liu, H., et al. (2016), “A partially linear framework for massive heteroge- neous data,”The Annals of Statistics, 44, 1400–1437. 12 Supplement to: Rates of Convergence for Large-scale Nearest Neighbor Classiﬁcation Xingye Qiao, Jiexin Duan, and Guang Cheng...

2016

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Optimizing parallel algorithms for all pairs similarity search,

Alabduljalil, M. A., Tang, X., and Yang, T. (2013), “Optimizing parallel algorithms for all pairs similarity search,” in Proceedings of the sixth ACM international conference on Web search and data mining, ACM, pp. 203–212

work page 2013

[2] [2]

Parallel cosine nearest neighbor graph construction,

Anastasiu, D. C. and Karypis, G. (2017), “Parallel cosine nearest neighbor graph construction,” Journal of Parallel and Distributed Computing

work page 2017

[3] [3]

Fast learning rates for plug-in classiﬁers,

Audibert, J.-Y . and Tsybakov, A. B. (2007), “Fast learning rates for plug-in classiﬁers,”Ann. Statist., 35, 608–633. 9

work page 2007

[4] [4]

Searching for exotic particles in high-energy physics with deep learning,

Baldi, P., Sadowski, P., and Whiteson, D. (2014), “Searching for exotic particles in high-energy physics with deep learning,”Nature communications, 5, 4308

work page 2014

[5] [5]

Distributed Estimation and Inference with Statistical Guarantees

Battey, H., Fan, J., Liu, H., Lu, J., and Zhu, Z. (2015), “Distributed estimation and inference with statistical guarantees,”arXiv preprint arXiv:1509.05457

work page Pith review arXiv 2015

[6] [6]

Multidimensional binary search trees used for associative searching,

Bentley, J. L. (1975), “Multidimensional binary search trees used for associative searching,” Communications of the ACM, 18, 509–517

work page 1975

[7] [7]

Bagging predictors,

Breiman, L. (1996), “Bagging predictors,” Machine learning, 24, 123–140

work page 1996

[8] [8]

Accurate occupancy detection of an ofﬁce room from light, temperature, humidity and CO2 measurements using statistical learning models,

Candanedo, L. M. and Feldheim, V . (2016), “Accurate occupancy detection of an ofﬁce room from light, temperature, humidity and CO2 measurements using statistical learning models,” Energy and Buildings, 112, 28–39

work page 2016