A scalable version of MADD for big-data classification

Adrija Saha; Annesha Ghosh; Soham Sarkar

REVIEW 2 major objections 4 minor 27 references

A scalable version of MADD for big-data classification

T0 review · 2 major / 4 minor · reviewed 2026-07-10 · grok-4.5

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

Pith's one-line read A small diverse subset of training points makes MADD-based nearest-neighbor classification fast enough for large high-dimensional data without losing accuracy.

desk verdict Solid engineering that makes MADD usable for large n, with strong empirics and a theory section the authors correctly flag as incomplete. read the letter →

arxiv 2607.08334 v1 pith:XY5MRJXX submitted 2026-07-09 stat.ME stat.COstat.ML

Annesha Ghosh , Adrija Saha , Soham Sarkar This is my paper

classification stat.MEstat.COstat.ML MSC 62H3062G99

keywords MADDscalableclassificationdeterminantalpointprocessRandomFourierFeatureshigh-dimensionaldatanearestneighborcross-validationbig

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Share X Bluesky LinkedIn Reddit HN

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

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.

What 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.

Citation 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.

Referee Report

2 major / 4 minor

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).

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 imes, 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 (2)

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 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.

minor comments (4)

Section 8 (Concluding Remarks): “generlized” should be “generalized”.
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.
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.
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.

Circularity Check

1 steps flagged · score 1.0 of 10

No material circularity: Prop. 1 is a conditional agreement statement whose premises are not forced by definition or by a self-citation uniqueness claim; self-cites supply only background HDLSS properties of full MADD.

self citation load bearing [Section 7, paragraph after Proposition 1 (and Remark 4)]
"This type of convergence is well known for ρ̃ in the HDLSS regime, which is a ramification of the class separation property of MADD (Pal et al., 2016; Sarkar and Ghosh, 2020)."

The positive-margin premise γ̃_n(Z)→γ>0 that makes Proposition 1 non-vacuous is justified solely by citations to earlier papers sharing co-authors (Sarkar, Ghosh). The citations are not machine-checked uniqueness theorems and are not re-proved here; they simply import the known HDLSS behaviour of full MADD. The step is minor because the paper’s novel claim is the scalable approximation, not a new uniqueness result, and the premise remains an explicit assumption rather than a forced tautology.

full rationale

The derivation chain for the scalable classifier is definitional (MADD_sc averages absolute distance differences over a DPP-selected subset X*) followed by a standard concentration argument (Lemma 1 bounds the sampling fluctuation of the DPP mean by O_P(√(log n/k*))) and a high-dimensional heuristic for the bias term. Proposition 1 then states that agreement of NN-MADD_sc with NN-MADD holds whenever the uniform approximation error β̃_n(Z)→0 and the full-MADD margin γ̃_n(Z) stays bounded away from zero. Neither premise is obtained by fitting a free parameter to the very quantity later called a “prediction,” nor is either premise declared unique by a self-citation theorem. The γ̃_n→γ>0 claim is imported from earlier MADD papers (Pal et al. 2016; Sarkar & Ghosh 2020) that share co-authors, but those citations establish only the well-known class-separation property of the full semi-metric; they do not force the new approximation result. Hyper-parameters (k_j via incremental CV, D=500 for RFF, median bandwidth) are chosen independently of the final error tables. The authors themselves label the bias control “admittedly incomplete,” which is a correctness gap, not a circular reduction. Empirical tables compare misclassification rates against external baselines (GLMNET, RF, SVM, etc.) on held-out data, confirming that the method is not tautological. Hence the circularity score remains minimal.

Assumptions & free parameters 3 free parameters · 4 assumptions · 2 invented entities

The central claim rests on classical high-dimensional concentration of Euclidean distances (imported from Hall et al., Pal et al.), the repulsion property of L-ensembles / k-DPPs (Kulesza & Taskar), Bochner’s theorem for RFF (Rahimi & Recht), and the unproved uniform approximation β̃_n(Z)→0. Free parameters are the representative sizes k_j (chosen by CV), the RFF dimension D=500, and the median-heuristic bandwidths. No new physical entities are postulated; the invented objects are purely algorithmic.

free parameters (3)

representative sizes k_j (or k_jt grid)
Chosen by 5-fold incremental CV over the grid k_jt = 2^{t-3} √d (n_j/n) log n_j; the functional form is motivated by the theory but the constants and the grid itself are free design choices that affect both accuracy and runtime.
RFF dimension D
Fixed at D=500 in all large-n experiments; controls approximation quality of the Gaussian kernel and therefore of the DPP sample.
Gaussian bandwidth σ_j
Set by the median heuristic σ_j = median{‖X_ji − X_ji′‖}; a standard but still free choice that scales the similarity matrix.

assumptions (4)

domain assumption High-dimensional concentration of pairwise Euclidean distances: d^{-1/2}‖X−Y‖ converges in probability to constants determined by class means and traces of covariances (Hall et al. 2005, Pal et al. 2016).
Used throughout Sections 1–2 and 7 to argue that a small representative set already captures the positive MADD separation between classes.
standard math k-DPP / L-ensemble samples are diverse (repulsion) and the associated indicator vectors are strongly Rayleigh, permitting concentration inequalities (Pemantle & Peres 2014).
Invoked in Lemma 1 (Appendix B) to bound the Monte-Carlo error of the representative-set average.
standard math Bochner’s theorem: continuous shift-invariant kernels are Fourier transforms of probability measures, justifying Monte-Carlo RFF approximation of the Gaussian kernel.
Foundation of Algorithm 2 and the claim that L ≈ RR^⊤ with moderate D.
ad hoc to paper β̃_n(Z) → 0 in probability (uniform approximation of full MADD by the scalable version).
Assumed for Proposition 1; only partially proved (sampling error controlled, bias term heuristic) and mainly supported by numerical box-plots.

invented entities (2)

MADD_sc (scalable MADD) and gMADD_sc
purpose: Redefine the semi-metric using only a DPP-selected representative subset so that complexity drops from O(n^{2}d) to O(k n d).
Purely algorithmic constructions; no independent physical existence claimed.
Incremental ordered-DPP cross-validation
purpose: Select the hyper-parameters k_j without recomputing MADD from scratch for every candidate size.
Algorithmic device that exploits the nested structure of the deterministic top-k eigenvector selection.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A scalable version of MADD for big-data classification." pith.science (2026). https://pith.science/paper/XY5MRJXX

@misc{pith2026260708334,
  author       = {Pith},
  title        = {Pith review of: A scalable version of MADD for big-data classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XY5MRJXX}},
  note         = {Machine review of arXiv:2607.08334}
}

read the original abstract

Distance-based classifiers are very popular, and the Euclidean distance is one of the most commonly used metrics in distance-based classifiers. However, classifiers based on the Euclidean distance often suffer in high-dimensional setups due to issues such as distance concentration, violation of neighborhood structures, and the presence of hubs. In high-dimension, low-sample-size (HDLSS) situations, a data-driven semi-metric called the Mean Absolute Difference of Distances (MADD) is known to circumvent these issues. But one major problem with MADD is that its computational complexity increases quadratically with the training sample size. As a result, the application of MADD becomes computationally challenging for big datasets that have both a high dimension as well as a large number of observations. In this paper, we propose a scalable version of MADD that significantly reduces its computational complexity while retaining its advantages. This speed-up is achieved by selecting a representative set during the computation of MADD. Further speed-ups are achieved by using the idea of Random Fourier Features, particularly when the sample size is very large. We establish that our proposed methods achieve performances similar to MADD but only at a fraction of its computing time, both theoretically as well as numerically. Our approach broadens the scope of MADD, allowing its use to big-data with a very large number of observations.

Figures

Figures reproduced from arXiv: 2607.08334 by the authors.

**Figure 2.** Time series plot of Synthetic Control Chart data. [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

**Figure 3.** Time series plot of Mote Strain data. (two successive down movements), UD (up followed by down), DU (down followed by up), and UU (two successive up movements). The observations are plotted in [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

Figures from the paper (6 more)

**Figure 4.** Figure 4: Time series plot of Two Patterns data. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]

**Figure 5.** Figure 5: Time series plot of the Wafer data. Normal and Abnormal. The plot of the data in [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]

**Figure 6.** Figure 6: Time series plot of the Star Light Curves data. [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]

**Figure 7.** Figure 7: Time series plots of the Electric Devices data. [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]

**Figure 8.** Figure 8: Boxplots of βe(Z) values in Examples 2 and 5 for varying values of n and d. 8 Concluding Remarks In this paper, we propose a scalable version of the semi-metric mean absolute difference of distances (MADD) and its generlized version gMADD. Both MADD and gMADD are usefu…

**Figure 9.** Figure 9: Boxplots of βe(Z) values in Examples 1, 3, 4, 6 and 7 for varying n and d [PITH_FULL_IMAGE:figures/full_fig_p029_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

[1]

7th Hellenic

Time-series similarity queries employing a feature-based approach , author=. 7th Hellenic

work page
[2]

Nearest Neighbor

When Is “Nearest Neighbor” Meaningful? , author=. Proceedings of the 7th International Conference on Database Theory , pages=. 1999 , publisher=

work page 1999
[3]

, title =

Bishop, Christopher M. , title =. 2006 , series =

work page 2006
[4]

1933 , publisher=

Bochner, Salomon , journal=. 1933 , publisher=

work page 1933
[5]

Journal of the American Mathematical Society , volume=

Negative dependence and the geometry of polynomials , author=. Journal of the American Mathematical Society , volume=

work page
[6]

Biometrika , volume=

Scale adjustments for classifiers in high-dimensional, low sample size settings , author=. Biometrika , volume=. 2009 , publisher=

work page 2009
[7]

1977 , edition =

Sampling Techniques , author =. 1977 , edition =

work page 1977
[8]

2001 , edition =

Pattern Classification , author =. 2001 , edition =

work page 2001

Show all 27 references

[9]

arXiv preprint arXiv:1707.07269 , year=

Large Sample Analysis of the Median Heuristic , author=. arXiv preprint arXiv:1707.07269 , year=

arXiv
[10]

IEEE Transactions on Information Theory , volume =

The Reduced Nearest Neighbor Rule , author =. IEEE Transactions on Information Theory , volume =. 1972 , publisher =

1972
[11]

2002 , url =

Geurts, Pierre , title =. 2002 , url =

2002
[12]

2013 , edition =

Matrix Computations , author =. 2013 , edition =

2013
[13]

SIAM Review , volume=

Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions , author=. SIAM Review , volume=. 2011 , publisher=

2011
[14]

Journal of the Royal Statistical Society: Series B , volume=

Geometric representation of high dimension, low sample size data , author=. Journal of the Royal Statistical Society: Series B , volume=. 2005 , publisher=

2005
[15]

IEEE Transactions on Information Theory , volume =

The Condensed Nearest Neighbor Rule , author =. IEEE Transactions on Information Theory , volume =. 1968 , publisher =

1968
[16]

2009 , edition =

The Elements of Statistical Learning: Data Mining, Inference, and Prediction , author=. 2009 , edition =

2009
[17]

Foundations and Trends in Machine Learning , volume=

Determinantal point processes for machine learning , author=. Foundations and Trends in Machine Learning , volume=. 2012 , publisher=

2012
[18]

, title =

Olszewski, Robert T. , title =. 2001 , number =

2001
[19]

Pattern Recognition Letters , volume=

High dimensional nearest neighbor classification based on mean absolute differences of inter-point distances , author=. Pattern Recognition Letters , volume=. 2016 , publisher=

2016
[20]

Combinatorics, Probability and Computing , volume =

Robin Pemantle and Yuval Peres , title =. Combinatorics, Probability and Computing , volume =. 2014 , publisher =

2014
[21]

Journal of Machine Learning Research , volume=

Hubs in space: Popular nearest neighbors in high-dimensional data , author =. Journal of Machine Learning Research , volume=
[22]

Advances in Neural Information Processing Systems 20 , pages =

Rahimi, Ali and Recht, Benjamin , title =. Advances in Neural Information Processing Systems 20 , pages =
[23]

On generalizations of some distance based classifiers for

Roy, Sarbojit and Sarkar, Soham and Dutta, Subhajit and Ghosh, Anil K , journal=. On generalizations of some distance based classifiers for
[24]

Machine Learning , volume=

On some graph-based two-sample tests for high dimension, low sample size data , author=. Machine Learning , volume=. 2020 , publisher=

2020
[25]

IEEE Transactions on Pattern Analysis and Machine Intelligence , volume=

On perfect clustering of high dimension, low sample size data , author=. IEEE Transactions on Pattern Analysis and Machine Intelligence , volume=. 2020 , publisher=

2020
[26]

International Journal of Machine Learning and Cybernetics , volume=

Hubness-based fuzzy measures for high-dimensional k-nearest neighbor classification , author=. International Journal of Machine Learning and Cybernetics , volume=. 2014 , publisher=

2014
[27]

Williams, Christopher K. I. and Seeger, Matthias , title =. Advances in Neural Information Processing Systems 13 , pages =

Pith tools

Reviewed July 10, 2026 · model on record in the stance chip above.

[1] [1]

7th Hellenic

Time-series similarity queries employing a feature-based approach , author=. 7th Hellenic

work page

[2] [2]

Nearest Neighbor

When Is “Nearest Neighbor” Meaningful? , author=. Proceedings of the 7th International Conference on Database Theory , pages=. 1999 , publisher=

work page 1999

[3] [3]

, title =

Bishop, Christopher M. , title =. 2006 , series =

work page 2006

[4] [4]

1933 , publisher=

Bochner, Salomon , journal=. 1933 , publisher=

work page 1933

[5] [5]

Journal of the American Mathematical Society , volume=

Negative dependence and the geometry of polynomials , author=. Journal of the American Mathematical Society , volume=

work page

[6] [6]

Biometrika , volume=

Scale adjustments for classifiers in high-dimensional, low sample size settings , author=. Biometrika , volume=. 2009 , publisher=

work page 2009

[7] [7]

1977 , edition =

Sampling Techniques , author =. 1977 , edition =

work page 1977

[8] [8]

2001 , edition =

Pattern Classification , author =. 2001 , edition =

work page 2001