{"id":"394f4819-22bf-42a6-a58b-45253d8d9f02","arxiv_id":"2607.08334","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"DPP-selected representatives (plus RFF) yield a scalable MADD whose NN classifier matches full-MADD error rates at a fraction of the compute cost for large n and high d.","lead":"The paper introduces a scalable MADD semi-metric for nearest-neighbor classification that selects a small diverse representative set via determinantal point processes (and random Fourier features for huge n), cutting quadratic cost while matching full MADD accuracy. This makes an effective high-dimensional classifier practical for large-sample big data.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"The premise β̃_n(Z)→0 that underpins Proposition 1 is only heuristically controlled for the bias term, leaving the asymptotic agreement claim incompletely supported.","rationale":"The reader correctly isolates the incomplete justification of β̃_n(Z)→0 as the single load-bearing soft spot. All other pieces—DPP diversity, incremental CV, RFF approximation quality, extensive simulations and real-data tables—are carefully engineered and empirically solid; the code is public. No stronger internal inconsistency or hidden circularity appears. Consequently the CONDITIONAL verdict (high confidence) already reflects the precise status of the work: a genuine practical advance whose theoretical guarantee remains conditional on an unclosed gap that the authors themselves flag. No adjustment is required.","tokens_in":37635,"tokens_out":547,"duration_ms":17987,"concrete_test":"Under the classical HDLSS assumptions of Hall et al. (2005) (component-wise moments, trace-normalized covariances), derive an explicit high-probability bound on the bias term that appears after Eq. (8). If the bound fails to be o_p(1) for the paper’s choice k_j∝√d(n_j/n)log n_j, the premise of Proposition 1 is unsupported and the theoretical half of the central claim collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 1 (Section 7) states that NN-MADD_sc and NN-MADD agree with probability →1 (and their risks converge) once the uniform approximation error β̃_n(Z)≔sup|ρ̃_sc−ρ̃|→0 in probability and the full-MADD margin γ̃_n(Z) stays bounded away from zero. Lemma 1 cleanly bounds the Monte-Carlo fluctuation of the DPP sample mean by O_P(√(log n/k*)). The remaining bias term sup|μ̂_p−ρ̃|, however, is controlled only by a high-dimensional concentration heuristic (pairwise scaled distances converge to class-dependent constants a_{jj′}, so the weighted average collapses when k_j/k*−n_j/n→0) plus the numerical box-plots of Figure 8. The authors themselves label the argument “admittedly incomplete” and “admittedly strong.” Because the strongest theoretical claim of the paper rests exactly on this unproved uniform approximation, any failure of the bias term to vanish would invalidate the asymptotic equivalence even when the sampling error is negligible.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proposes scalable versions of the MADD and gMADD semi-metrics for nearest-neighbor classification in high-dimensional, large-sample regimes. Scalability is obtained by replacing the full training set in the MADD sum with a small diverse representative subset drawn via k-DPP (with an ordered deterministic variant enabling incremental cross-validation for the subset sizes k_j), and by further approximating the DPP kernel via Random Fourier Features when n is very large. The authors claim that the resulting NN-MADD_sc (and NN-gMADD_sc) classifiers retain the neighborhood-structure advantages of full MADD while reducing complexity from O(n^{2}d) to O(knd) (or better with RFF), and they support this with extensive simulations, UCR time-series experiments, runtime tables, and a conditional asymptotic-agreement result (Proposition 1).","tokens_in":37960,"tokens_out":993,"duration_ms":18205,"significance":"If the claims hold, the work removes the principal practical barrier that has confined MADD/gMADD to HDLSS settings and thereby makes a theoretically well-motivated distance usable for modern high-d, large-n classification problems (gene expression, high-resolution images, long time series). The empirical package is strong: error rates stay within ~1 % of full MADD across seven carefully chosen regimes and many UCR archives, standard errors are reported, runtimes drop by factors of 3–40\times, and code is released. The incremental ordered-DPP CV and the RFF-DPP pipeline are reusable technical contributions. The theoretical guarantee is weaker (conditional on an incompletely justified uniform approximation), yet the numerical evidence already makes the method immediately usable.","major_comments":[{"comment":"Section 7, Proposition 1 and the surrounding discussion of β̃_n(Z) (Eqs. 6–8 and Lemma 1): the asymptotic agreement of NN-MADD_sc with NN-MADD rests on the load-bearing premise that the uniform approximation error β̃_n(Z) → 0 in probability. Lemma 1 cleanly controls only the Monte-Carlo fluctuation of the DPP sample mean by O_P(√(log n/k*)). The bias term involving inclusion probabilities is handled solely by a high-dimensional concentration heuristic (pairwise scaled distances concentrate to class-dependent constants) plus the numerical box-plots of Figures 8–9; the authors themselves label the argument “admittedly incomplete” and “admittedly strong.” Because the abstract and introduction claim that similarity is established “both theoretically as well as numerically,” this gap must be closed or the theoretical claim must be substantially weakened.","section":null},{"comment":"Section 4 and Algorithm 2: the RFF approximation (D = 500) is used for the largest-n experiments and is essential to the “massive data” claim, yet no quantitative guarantee is given that the approximate k-DPP still produces a representative set whose MADD_sc distances remain close to those of the exact DPP (or to full MADD). Relative Frobenius errors of the kernel matrices are reported, but the effect on the subsequent classification risk is left unanalyzed; a short concentration or stability argument would strengthen the central scalability claim.","section":null}],"minor_comments":[{"comment":"Section 8 (Concluding Remarks): “generlized” should be “generalized”.","section":null},{"comment":"Table 1 and subsequent runtime tables: units are seconds, but the hardware description appears only once; a short note that all timings share the same platform would aid reproducibility.","section":null},{"comment":"Remark 4 and the choice k_j ∝ √d (n_j/n) log n_j: the factor √d is motivated heuristically; a brief sensitivity check with log d or constant factors would reassure readers that the CV grid is not overly tuned.","section":null},{"comment":"Figure 1 caption and surrounding text: the bivariate examples are helpful, yet the color/marker legend is repeated only in the caption; placing it once in the figure itself would improve readability.","section":null}],"recommendation":"major_revision","confidential_remarks":"The empirical work is solid and the method is practically useful; the main obstacle to acceptance is the mismatch between the strong theoretical language in the abstract and the incomplete justification of β̃_n → 0. A revision that either supplies a rigorous bias bound or candidly downgrades the theoretical claim to a conditional result would make the paper suitable for a methods journal. Scope is appropriate for stat.ME / machine-learning methodology venues."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The practical contribution is real: they take MADD (and gMADD), replace the full training set with a small DPP-selected representative set, add an ordered-DPP incremental CV for the k_j’s, and use RFF so the similarity-matrix eigenstep stays feasible when n is tens of thousands. Empirically it works. Across seven simulation regimes and a large UCR collection the error stays within roughly 1 % of full MADD while wall-clock drops by large factors; code is public and the tables report standard errors. That is the part that matters for people who actually want to run these classifiers on big high-dim data.\n\nWhat is new is the combination and the incremental CV trick, not the individual ingredients. DPP, RFF and MADD itself are prior art; the paper is honest about that. The theory (Proposition 1) is cleanly stated: if the uniform approximation error β̃_n goes to zero and the full-MADD margin stays positive, the two classifiers agree asymptotically. Lemma 1 handles the sampling fluctuation; the bias term is controlled only by a high-dimensional concentration heuristic plus the box-plots in Figures 8–9. The authors themselves call the analysis “admittedly incomplete.” That is the soft spot, and it is exactly as soft as they say—no more, no less. It does not sink the paper; it just means the asymptotic claim is conditional rather than fully proved.\n\nCitation pattern is appropriate, methods are reproducible, free parameters are either cross-validated or fixed by standard heuristics. No circularity or data issues. This is for people working on high-dimensional distance-based classification who need something that scales. I would send it to referees; the empirics and the engineering are strong enough to deserve a careful look, and the theory gap is already flagged so referees can decide how much weight to give it.","headline":"Solid engineering that makes MADD usable for large n, with strong empirics and a theory section the authors correctly flag as incomplete.","tokens_in":38573,"tokens_out":473,"would_cite":true,"duration_ms":6702,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30","62G99"],"pacs":[],"model":"grok-4.5","headline":"A small diverse subset of training points makes MADD-based nearest-neighbor classification fast enough for large high-dimensional data without losing accuracy.","keywords":["MADD","scalable classification","determinantal point process","Random Fourier Features","high-dimensional data","nearest neighbor","cross-validation","big data"],"falsifier":"Generate high-dimensional data from two populations that differ only in location or scale, compute both full NN-MADD and NN-MADDsc on the same training set, and check whether the fraction of test points on which the two classifiers disagree stays near zero while the representative-set size grows only like sqrt(d) log n; a systematic growth of that disagreement fraction would refute the claimed asymptotic agreement.","tokens_in":38520,"feed_emoji":"⚡","tokens_out":698,"duration_ms":7141,"temperature":0.7,"pith_summary":"Euclidean nearest-neighbor classifiers break down in high dimensions because distances concentrate, neighborhood structure is lost, and hubs appear. The earlier semi-metric MADD restores correct neighborhoods when populations differ in location or scale, but its cost grows with the square of the sample size and becomes prohibitive once both dimension and sample size are large. This paper shows that one need not average absolute distance differences over every training point: a carefully chosen representative subset already preserves the asymptotic separation property. Determinantal point processes select a diverse subset that mirrors the geometry of each class; an incremental cross-validation rule chooses how large that subset must be; and Random Fourier Features make the selection itself feasible when the sample is huge. The resulting scalable classifier matches ordinary MADD error rates to within roughly one percent while cutting run times by large factors, thereby extending a useful high-dimensional tool to genuine big-data regimes.","feed_headline":"Tiny diverse subset makes MADD classifiers scale to big data","feed_subtitle":"Error stays within 1% of full MADD while run time drops from hours to minutes","key_machinery":"Scalable MADD (MADDsc): the average of absolute differences of Euclidean distances taken only over a representative subset X* of size k ≪ n, where X* is drawn by class-wise k-DPP with a Gaussian kernel (median bandwidth) and k itself is chosen by an incremental ordered cross-validation that re-uses previously computed distances.","core_discovery":"Replacing the full training set inside the definition of MADD by a small, diverse representative set selected by k-DPP yields a semi-metric whose nearest-neighbor classifier agrees with classical NN-MADD with probability tending to one (under a vanishing uniform approximation error and a positive margin) and whose empirical misclassification rates stay within about one percent of the full method while the computational complexity drops from quadratic to linear in the sample size times the (much smaller) representative-set size.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Small k-DPP subset makes MADD linear-time for big data","Diverse reps turn quadratic MADD into scalable NN classifier","k-DPP selection yields near-identical MADD accuracy far faster","Tiny representative set cuts MADD cost while matching full rates","Scalable MADD via k-DPP reps agrees with classical NN-MADD"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The uniform gap between full MADD and its representative-set version must vanish in probability; the paper only rigorously bounds the sampling fluctuation and relies on a high-dimensional concentration heuristic plus numerical checks for the remaining bias.","fun_headline_variants_meta":{"raw":{"variants":["Small k-DPP subset makes MADD linear-time for big data","Diverse reps turn quadratic MADD into scalable NN classifier","k-DPP selection yields near-identical MADD accuracy far faster","Tiny representative set cuts MADD cost while matching full rates","Scalable MADD via k-DPP reps agrees with classical NN-MADD"]},"model":"grok-4.5","effort":"low","cost_usd":0.004602,"raw_usage":{"total_tokens":1341,"prompt_tokens":813,"num_sources_used":0,"completion_tokens":95,"cost_in_usd_ticks":46020000,"prompt_tokens_details":{"text_tokens":813,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":433,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":813,"tokens_out":95,"duration_ms":4244,"temperature":1.0,"reasoning_tokens":433,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T09:12:33.172637+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Generate high-dimensional data from two populations that differ only in location or scale, compute both full NN-MADD and NN-MADDsc on the same training set, and check whether the fraction of test points on which the two classifiers disagree stays near zero while the representative-set size grows only like sqrt(d) log n; a systematic growth of that disagreement fraction would refute the claimed asymptotic agreement.","supporting_citations":[],"review_version":1}