A scalable version of MADD for big-data classification

• URL: http://arxiv.org/abs/2607.08334v1
• Date: Thu, 09 Jul 2026 10:19:57 GMT
• Title: A scalable version of MADD for big-data classification
• Abstract summary: In high-dimensional, low-sample-size situations, a data-driven semi-metric called the Mean Absolute Difference of Distances (MADD) is known to circumvent these issues.<n>We propose a scalable version of MADD that significantly reduces its computational complexity while retaining its advantages.
• Score: 0.7837881800517111
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• High-dimensional Semi-supervised Classification via the Fermat Distance [0.0]
  Semi-supervised classification, where unlabeled data are massive but labeled data are limited, often arises in machine learning applications.<n>We propose the weighted $k$-nearest neighbors (NN) classifier and multidimensional scaling (MDS)-induced classifiers.<n>We explicitly quantify the utility of unlabeled data by showing that the error arising from estimating the Fermat distance decays exponentially with the pooled sample size.
  arXiv  Detail & Related papers  (2026-04-26T07:28:21Z)
• Model-Based and Sample-Efficient AI-Assisted Math Discovery in Sphere Packing [51.30643063554434]
  A leading technique for upper bounds, the three-point method, reduces the problem to solving large, high-precision semidefinite programs (SDPs)<n>We formulate SDP construction as a sequential decision process, the SDP game, in which a policy assembles SDP formulations from a set of admissible components.<n>We obtain new state-of-the-art upper bounds in dimensions $4-16$, showing that model-based search can advance computational progress in longstanding geometric problems.
  arXiv  Detail & Related papers  (2025-12-04T14:11:52Z)
• Bias Detection via Maximum Subgroup Discrepancy [2.236957801565796]
  We propose a new notion of distance, the Maximum Subgroup Discrepancy (MSD)<n>In this metric, two distributions are close if, roughly, discrepancies are low for all feature subgroups.<n>We show that the sample complexity is linear in the number of features, thus making it feasible for practical applications.
  arXiv  Detail & Related papers  (2025-02-04T11:01:03Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach.<n>Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Multiscale Dubuc: A New Similarity Measure for Time Series [1.024113475677323]
  We introduce the Multiscale Dubuc Distance measure and prove that it is a metric. We use 95 datasets from the UCR Time Series Classification Archive to compare MDD's performance with EuD, LCSS, and DTW. Our experiments show that MDD's overall success, without any case-specific customization, is comparable to DTW with optimized window sizes per dataset.
  arXiv  Detail & Related papers  (2024-11-15T18:38:18Z)
• Scaling Riemannian Diffusion Models [68.52820280448991]
  We show that our method enables us to scale to high dimensional tasks on nontrivial manifold. We model QCD densities on $SU(n)$ lattices and contrastively learned embeddings on high dimensional hyperspheres.
  arXiv  Detail & Related papers  (2023-10-30T21:27:53Z)
• Bayesian Hyperbolic Multidimensional Scaling [2.5944208050492183]
  We propose a Bayesian approach to multidimensional scaling when the low-dimensional manifold is hyperbolic. A case-control likelihood approximation allows for efficient sampling from the posterior distribution in larger data settings. We evaluate the proposed method against state-of-the-art alternatives using simulations, canonical reference datasets, Indian village network data, and human gene expression data.
  arXiv  Detail & Related papers  (2022-10-26T23:34:30Z)
• AdAUC: End-to-end Adversarial AUC Optimization Against Long-tail Problems [102.95119281306893]
  We present an early trial to explore adversarial training methods to optimize AUC. We reformulate the AUC optimization problem as a saddle point problem, where the objective becomes an instance-wise function. Our analysis differs from the existing studies since the algorithm is asked to generate adversarial examples by calculating the gradient of a min-max problem.
  arXiv  Detail & Related papers  (2022-06-24T09:13:39Z)
• Accelerated Computation of a High Dimensional Kolmogorov-Smirnov Distance [0.0]
  We extend the powerful Kolmogorov-Smirnov two sample test to a high dimensional form. We call our result the d-dimensional Kolmogorov-Smirnov test (ddKS)
  arXiv  Detail & Related papers  (2021-06-25T15:45:18Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping [57.316437798033974]
  In this work we consider the problem of center-based clustering of trajectories. We propose the usage of a continuous version of DTW as distance measure, which we call continuous dynamic time warping (CDTW) We show a practical way to compute a center from a set of trajectories and subsequently iteratively improve it.
  arXiv  Detail & Related papers  (2020-12-01T13:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.