{"id":"171fb81a-365b-4273-b09b-6b1ec633107a","arxiv_id":"1909.01464","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A distributed k-nearest-neighbor classifier that pools local predictions by majority vote attains the same minimax-optimal excess risk and instability rates as the oracle full-data kNN classifier.","lead":"This paper proves that a divide-and-conquer nearest neighbor classifier, which splits big data into small pieces and combines local predictions by majority vote, reaches the same optimal error rates as running nearest neighbors on the full data set. It also analyzes a pre-training acceleration that cuts prediction time sharply at a small accuracy cost.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof is internally consistent, but the Hölder-minimax comparison relies on the unproven transition (1): without a density lower bound, μ(B(x,r)) can be o(r^d), so Euclidean-Hölder η need not be (α,L)-smooth at the kNN scale; the claimed optimality then lacks support.","rationale":"I read the paper as proving a conditional rate theorem: whenever the (α,L)-smoothness of η with respect to μ and the β-margin condition hold, the bigNN regret is O(N^{-α(β+1)/(2α+1)}). Tracing the supplement, the proof is coherent: Lemma 1 uses the smoothness only at radii r≤r_p(x), the Chernoff bound over s independent local classifiers is applied correctly, and the dyadic margin decomposition balances Δo and (ks)^{-1/2} to the claimed exponent. I do not find a step that invalidates the conditional theorem. The load-bearing weakness is the paper's use of equation (1) to translate this into the known Hölder minimax rate and to claim optimality under 'minimal assumptions'. That translation requires μ to have a uniformly positive d-dimensional density locally, which is not stated and is false for measures with atoms or vanishing density. In such cases a smooth η can fail the μ-smoothness condition at the precise scale used in the proof, so the claimed equivalence with the oracle/minimax Hölder rate is not established. This is a real but scope-level concern; it warrants a caveat rather than a rejection, so the reader's CONDITIONAL verdict stands unchanged.","tokens_in":19440,"tokens_out":23287,"duration_ms":233694,"concrete_test":"Let X=[0,1], μ(dx)=3x^2 dx (density vanishing at 0), and η(x)=x, so η is 1-Hölder. Set d=1, αH=1, so (1) would give α=1. For the pair (0,x), μ(Bo(0,x))=x^3, while |η(0)-η(x)|=x; the required inequality x ≤ L x^3 fails for all finite L as x→0. Thus η is not (1,L)-smooth w.r.t. μ, and the proof of Lemma 1 cannot be applied at the kNN scale. Re-running Theorem 1 for this μ would show the N^{-(β+1)/3} Hölder rate is not justified, demonstrating that a density-lower-bound hypothesis is needed for the transition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central rate (Theorem 1) is obtained in the supplement through Lemma 1, whose pointwise bound requires the (α,L)-smoothness inequality at ball radii down to r_p(x) with p=2k/n. This is a joint condition on (η,μ), not a property of η alone. The bridge to the familiar Hölder rates is equation (1), α=αH/d, which the paper presents as an implication of Hölder continuity. That implication is false without a uniform lower bound μ(B(x,r)) ≥ c r^d (e.g., a density bounded below on the support). With atoms, singular components, or density vanishing in a region, μ(Bo(x,ρ)) can be much smaller than ρ^d, so a Euclidean-Hölder η can violate the μ-smoothness inequality exactly at the scales where the local kNN ball has probability mass p. In such cases Theorem 1's rate is not obtained and the claimed minimax optimality over Hölder classes is not established. This is a limitation of the scope of the headline claim, not an internal contradiction in the proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19625,"tokens_out":11880,"duration_ms":118184,"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":[{"comment":"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.","section":"Section 2, Eq. (1)"},{"comment":"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.","section":"Supplement, proof of Theorem 3"}],"minor_comments":[{"comment":"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":"Section 3, Theorem 1"},{"comment":"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.","section":"Section 4"},{"comment":"The expression 'δ4/s/4' is ambiguous; it should be written as δ^{4/s}/4 or with explicit parentheses.","section":"Supplement, proof of Theorem S.1"},{"comment":"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.","section":"Section 5, Simulation 1"}],"recommendation":"major_revision","confidential_remarks":"The rate proofs under the (α,L)-smoothness assumption appear sound, and the divide-and-conquer result is a reasonable contribution. The main risk is the Hölder-bridge overclaim; fixing it may require adding a density lower bound or weakening the optimality statements. The Theorem 3 proof gap is more than cosmetic and should be addressed carefully. I would not reject if the authors repair these points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhere 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.\n\nNow 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.\n\nSecond, 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.\n\nBottom 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.\n\nRecommendation: engage with it. It is worth citing for the bigNN rate, with a note on the density condition.","headline":"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.","tokens_in":20226,"tokens_out":5638,"would_cite":true,"duration_ms":54834,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30","62G08","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["nearest neighbor classification","divide and conquer","majority voting","distributed learning","excess risk","classification instability","margin condition","minimax convergence rate"],"falsifier":"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.","tokens_in":19175,"feed_emoji":"🗳️","tokens_out":7683,"duration_ms":73015,"temperature":0.7,"pith_summary":"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.","feed_headline":"Divide-and-conquer kNN keeps the optimal error rate","feed_subtitle":"Majority-voting over subsamples reaches the same minimax rate as full-data kNN, with a limit on split count.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the $(\\alpha,L)$-smoothness condition, the effective-boundary technique, and the oracle kNN rate that bigNN is compared against.","marker":"[9]"},{"why":"Establishes the minimax lower bound under the margin condition that shows the bigNN rate is sharp.","marker":"[3]"},{"why":"Introduces the denoising/pre-training acceleration scheme and the nearest-neighbor distance lemma used in Theorem 3.","marker":"[45]"},{"why":"Defines classification instability (CIS) and provides the oracle CIS rate that Theorem 2 matches.","marker":"[41]"},{"why":"Provides the optimal weighted nearest-neighbor baseline that also achieves the optimal rate and is used as a comparison in the real-data study.","marker":"[37]"}],"fun_headline_variants":["Suboptimal local kNNs, optimal global rate via voting","Big kNN matches oracle rate, but split count has a limit","Divide-and-conquer kNN hits minimax bound, with a cap on splits","Majority voting over subsamples preserves kNN optimality"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Suboptimal local kNNs, optimal global rate via voting","Big kNN matches oracle rate, but split count has a limit","Divide-and-conquer kNN hits minimax bound, with a cap on splits","Majority voting over subsamples preserves kNN optimality"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000802,"raw_usage":{"total_tokens":3570,"prompt_tokens":1032,"completion_tokens":2538,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":648,"completion_tokens_details":{"reasoning_tokens":2463}},"tokens_in":648,"tokens_out":2538,"duration_ms":17730,"temperature":1.0,"reasoning_tokens":2463,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:17:59.880234+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Rates of convergence for nearest neighbor classifica- tion,","cited_arxiv_id":null,"evidence_quote":"Supplies the $(\\alpha,L)$-smoothness condition, the effective-boundary technique, and the oracle kNN rate that bigNN is compared against."},{"cited_title":"Fast learning rates for plug-in classifiers,","cited_arxiv_id":null,"evidence_quote":"Establishes the minimax lower bound under the margin condition that shows the bigNN rate is sharp."},{"cited_title":"Achieving the time of 1-NN, but the accuracy of k-NN,","cited_arxiv_id":null,"evidence_quote":"Introduces the denoising/pre-training acceleration scheme and the nearest-neighbor distance lemma used in Theorem 3."},{"cited_title":"Stabilized Nearest Neighbor Classifier and its Statistical Properties,","cited_arxiv_id":null,"evidence_quote":"Defines classification instability (CIS) and provides the oracle CIS rate that Theorem 2 matches."},{"cited_title":"Optimal weighted nearest neighbour classifiers,","cited_arxiv_id":null,"evidence_quote":"Provides the optimal weighted nearest-neighbor baseline that also achieves the optimal rate and is used as a comparison in the real-data study."}],"review_version":1}