📊 statistics

A scalable version of MADD for big-data classification

This paper proposes a scalable version of the Mean Absolute Difference of Distances (MADD) classifier that significantly reduces computational complexity for big-data classification by utilizing representative set selection and Random Fourier Features, thereby enabling its application to large-scale, high-dimensional datasets while maintaining performance comparable to the original method.

Original authors: Annesha Ghosh, Adrija Saha, Soham Sarkar

Published 2026-07-10

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Annesha Ghosh, Adrija Saha, Soham Sarkar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the "closest friend" to a new person walking into a crowded room. In the world of computer science, this is called classification: figuring out which group a new data point belongs to by seeing which group it is closest to.

For a long time, computers used a simple ruler called Euclidean distance to measure this closeness. But here's the twist: in high-dimensional worlds (think of data with hundreds or thousands of features, like gene sequences or high-res images), that ruler breaks down. It's like trying to judge who is closest in a room where everyone is standing so far apart that everyone looks equally far away. The computer gets confused, the "neighborhood" structure collapses, and the classification fails.

To fix this, scientists invented a smarter ruler called MADD (Mean Absolute Difference of Distances). Instead of just measuring the distance from A to B, MADD asks: "How does the distance from A to everyone else compare to the distance from B to everyone else?" If A and B are from the same group, this difference is tiny. If they are from different groups, the difference is huge. It's a brilliant trick that works perfectly in high dimensions.

But there's a catch.

MADD is a bit of a slowpoke. To measure the distance between two points, it has to look at every single other person in the room. If you have a small room (a small dataset), that's fine. But if you have a massive crowd (big data), MADD has to do a math problem for every single pair of people. The paper shows that if you have 16,384 training samples, MADD takes more than 6.5 hours just to classify 5,000 new people. That's like trying to find a needle in a haystack by checking every single straw one by one with a magnifying glass. It works, but it's painfully slow.

The Big Idea: The "Representative Squad"

The authors of this paper asked: "Do we really need to ask everyone in the crowd? Or can we just ask a few smart representatives?"

They proposed a scalable version of MADD (called MADDsc). Instead of comparing the new person to all 16,384 people, the computer picks a tiny, super-smart "squad" of representatives. This squad is chosen using a fancy math tool called a Determinantal Point Process (DPP).

Think of DPP as a very picky party planner. If you ask a random person to pick a group of friends, they might pick five people who all sit in the same corner and look exactly alike. But DPP is different; it actively avoids picking similar people. It ensures the squad has a mix of people from different corners of the room, capturing the whole vibe of the crowd without needing to talk to everyone.

By using this squad (which might be as small as 50 or 100 people instead of thousands), the computer can do the MADD calculation in a fraction of the time.

The Result: In their tests, this new method was almost as accurate as the slow, original MADD, but it was massively faster. For a dataset of 4,096 samples, the new method took about 472 seconds, while the old method took 1,249 seconds. That's a huge speed-up!

The "Super-Speed" Trick for Giant Datasets

What if the crowd is so huge that even picking a squad takes too long? The authors added a second trick called Random Fourier Features (RFF).

Imagine you have a massive library of books, and you need to find similar ones. Instead of reading every page, you use a magical scanner that turns the text into a simple code. This code is short enough to fit in your pocket but still keeps the "essence" of the book. RFF does this for the math behind the squad selection.

When they tested this on a dataset with 25,000 training samples:

The original MADD method crashed because it ran out of memory (it literally couldn't hold the data).
The new MADDsc method (without the magic scanner) took over 15 hours.
The MADDsc method with the RFF magic scanner finished in less than 25 minutes (specifically, 1,468.68 seconds).

Did it actually work?

The authors didn't just guess; they ran 25 simulations for each scenario to be sure. They tested the method on:

Synthetic Data: Made-up data where they knew the answer.
Real Data: Real-world time-series data like heartbeats, electricity usage, and sensor readings from the UCR Time Series Classification Archive.

In the simulations, the new method (MADDsc) was consistently competitive, often beating other popular methods like Random Forests or Support Vector Machines, especially when the data had tricky shapes or mixtures. In the real-world tests, it performed very well, often coming in second or first place. For example, on the "Synthetic Control Chart" dataset, MADDsc made only 1.29% errors, beating the standard nearest-neighbor method which made 9.13% errors.

What They Didn't Do (And What They Avoided)

It's important to know what this paper didn't claim.

They ruled out simple random sampling (picking a squad by closing your eyes and pointing). They showed that random picks often miss the important structures in the data, leading to worse performance.
They did not claim that this works for every possible type of data forever. They noted that for a more complex version of their method (called gMADD), they couldn't yet use the "magic scanner" (RFF) trick because the math gets too tricky to figure out the right code. They suggest that might be a problem for future researchers to solve.
They did not say the method is "perfect" or "solved." They showed that in their specific simulations, the error rates were very close to the original slow method (usually within 1%), but the speed gain was the real hero.

The Bottom Line

The paper proves that you can have your cake and eat it too. You don't have to choose between a slow, accurate method and a fast, inaccurate one. By picking a smart, diverse "squad" of representatives instead of asking the whole crowd, and by using some clever math shortcuts for the biggest datasets, you can classify massive amounts of data quickly without losing accuracy.

As the authors showed in their tests, this approach allows us to use a powerful tool (MADD) on "big data" problems that were previously too slow or too memory-heavy to handle. It's a win for speed, and a win for accuracy, all while keeping the math honest.

Technical Summary: A Scalable Version of MADD for Big-Data Classification

Problem Statement
Distance-based classifiers, particularly those relying on the Euclidean distance, are fundamental to modern machine learning. However, in high-dimensional, low-sample-size (HDLSS) scenarios, Euclidean distance suffers from "distance concentration," where distances between points in the same class become larger than distances between points in different classes. This violates neighborhood structures and leads to the emergence of "hubs," severely degrading classifier performance.

To address this, Pal et al. (2016) introduced the Mean Absolute Difference of Distances (MADD), a data-driven semi-metric that successfully circumvents these high-dimensional issues by maintaining correct neighborhood structures based on location and scale differences. Despite its theoretical advantages, MADD faces a critical bottleneck: its computational complexity. Calculating MADD between two points requires $O(nd)$ operations (where $n$ is the training sample size and $d$ is dimensionality), and classifying a single test point via a Nearest Neighbor (NN) approach requires $O(n^2d)$ operations. As demonstrated in the paper, this quadratic scaling renders MADD computationally prohibitive for big datasets with large $n$ , even on modern hardware.

Methodology
The authors propose a scalable version of MADD, termed MADDsc, which significantly reduces computational complexity while retaining the statistical advantages of the original metric. The methodology consists of three core components:

Representative Set Selection via Determinantal Point Processes (DPP):
Instead of computing distances against the entire training set, MADDsc redefines the metric using a small, representative subset of observations, $X^* \subset X$ . The authors argue that the theoretical separation properties of MADD are preserved if the representative set captures the diversity of the original data.
- To select this set, the authors employ Determinantal Point Processes (DPP). Unlike simple random sampling, which may miss intrinsic data structures (especially in multimodal distributions), DPPs introduce a "repulsion" effect. By constructing a similarity matrix $L$ using a Gaussian radial basis kernel, DPPs select a subset of points that are diverse and spread out across the data cloud, ensuring the representative set captures the landscape of the full training sample.
- The computational cost is reduced from $O(n^2d)$ to $O(knd)$, where $k$ is the size of the representative set ( $k \ll n$ ).
Incremental Cross-Validation for Hyper-parameter Selection:
The size of the representative set ( $k$ ) is a crucial hyper-parameter. Standard cross-validation would require repeatedly selecting DPP samples and recomputing distances for every fold and candidate $k$ , negating the speed gains.
- The authors propose an incremental cross-validation technique. By modifying the DPP sampling algorithm to ensure that selected subsets are nested (i.e., $X^*(k_t) \subseteq X^*(k_{t+1})$ ), the MADDsc values can be computed incrementally. This allows the algorithm to update the metric as $k$ increases without re-computing the entire distance matrix, drastically reducing the computational overhead of model selection.
Random Fourier Features (RFF) for Massive Datasets:
For extremely large datasets where even the construction of the $n \times n$ similarity matrix for DPP is infeasible (due to memory or eigen-decomposition costs), the authors integrate Random Fourier Features (RFF).
- Based on Bochner's theorem, the Gaussian kernel is approximated via a Monte Carlo expectation. The similarity matrix $L$ is approximated by $R R^T$ , where $R$ is a low-dimensional feature map matrix ( $n \times 2D$ ).
- This allows the eigen-decomposition required for DPP sampling to be performed on a much smaller $2D \times 2D$ matrix (or via SVD of $R$ ), reducing both time and memory complexity. This approach is formalized as NN-MADDsc with RFF.

The framework is also extended to gMADDsc, a scalable version of the generalized MADD (gMADD), which handles cases where populations differ beyond just the first two moments (location and scale).

Key Results
Extensive simulation studies and real-data analyses on UCR Time Series datasets demonstrate the efficacy of the proposed methods:

Performance vs. Original MADD: In simulations across various distributions (location, scale, mixture, and heavy-tailed), NN-MADDsc achieves misclassification rates nearly identical to the original NN-MADD (differences typically $\le 1\%$ ).
Computational Efficiency:
- NN-MADDsc is significantly faster than NN-MADD. For a training size of $n=16,384$ , NN-MADD took over 6.5 hours, while NN-MADDsc completed in a fraction of that time.
- The incremental cross-validation strategy further reduces runtime compared to standard cross-validation, cutting computation time by nearly half for $n=4096$ .
- The RFF-based approach offers the most dramatic speedup. For $n=25,000$ , the RFF-based method completed in under 25 minutes, whereas the standard NN-MADDsc took over 15 hours, and the original NN-MADD failed due to memory constraints.
Comparison with Other Classifiers: NN-MADDsc consistently outperforms or matches state-of-the-art classifiers (including Random Forest, SVMs, and GLMNET) in high-dimensional settings, particularly when data distributions differ in shape or scale. In real-world time-series benchmarks, it achieved the lowest error rates in several datasets (e.g., Synthetic Control Chart, Two Patterns).
Theoretical Guarantees: The paper establishes that under high-dimension, high-sample-size (HDHSS) regimes, the classification decisions of NN-MADDsc converge to those of NN-MADD with probability tending to 1, provided the representative set size grows appropriately relative to the logarithm of the sample size.

Significance and Claims
The paper claims to broaden the scope of MADD, making it applicable to big-data scenarios characterized by both high dimensionality and large observation counts. The primary contribution is the decoupling of MADD's statistical robustness from its quadratic computational complexity. By leveraging DPPs for diversity-preserving subsampling and RFFs for kernel approximation, the authors provide a practical, scalable solution that retains the theoretical benefits of MADD in high-dimensional spaces. The work does not claim to replace all classifiers but positions MADDsc as a superior alternative for distance-based classification in regimes where Euclidean distance fails and traditional MADD is computationally intractable.