Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance

• URL: http://arxiv.org/abs/2504.11299v1
• Date: Tue, 15 Apr 2025 15:42:49 GMT
• Title: Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance
• Authors: Peter Matthew Jacobs, Foad Namjoo, Jeff M. Phillips,
• Abstract summary: We revisit extending the Kolmogorov-Smirnov distance between probability distributions to the multidimensional setting.<n>We prove that the distance between a distribution and a sample from the distribution converges to 0 as the sample size grows.
• Score: 7.326930455001404
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit extending the Kolmogorov-Smirnov distance between probability distributions to the multidimensional setting and make new arguments about the proper way to approach this generalization. Our proposed formulation maximizes the difference over orthogonal dominating rectangular ranges (d-sided rectangles in R^d), and is an integral probability metric. We also prove that the distance between a distribution and a sample from the distribution converges to 0 as the sample size grows, and bound this rate. Moreover, we show that one can, up to this same approximation error, compute the distance efficiently in 4 or fewer dimensions; specifically the runtime is near-linear in the size of the sample needed for that error. With this, we derive a delta-precision two-sample hypothesis test using this distance. Finally, we show these metric and approximation properties do not hold for other popular variants.

Related papers

• Bayesian Circular Regression with von Mises Quasi-Processes [57.88921637944379]
  In this work we explore a family of expressive and interpretable distributions over circle-valued random functions.<n>For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Gibbs sampling.<n>We present experiments applying this model to the prediction of wind directions and the percentage of the running gait cycle as a function of joint angles.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Quasi-Bayes meets Vines [2.3124143670964448]
  We propose a different way to extend Quasi-Bayesian prediction to high dimensions through the use of Sklar's theorem. We show that our proposed Quasi-Bayesian Vine (QB-Vine) is a fully non-parametric density estimator with emphan analytical form.
  arXiv  Detail & Related papers  (2024-06-18T16:31:02Z)
• Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
  Two estimators of linear functionals of $mu_phi $ based on the discretized Markov process are considered. Error bounds are derived for sampling and estimation using a discretization of an intrinsically defined Langevin diffusion.
  arXiv  Detail & Related papers  (2023-12-22T18:01:11Z)
• Robust Ellipsoid Fitting Using Axial Distance and Combination [15.39157287924673]
  In random sample consensus (RANSAC), the problem of ellipsoid fitting can be formulated as a problem of minimization of point-to-model distance. We propose a novel distance metric called the axial distance, which is converted from the algebraic distance. A novel sample-consensus-based ellipsoid fitting method is proposed by using the combination between the axial distance and Sampson distance.
  arXiv  Detail & Related papers  (2023-04-02T11:52:33Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Kernel distance measures for time series, random fields and other structured data [71.61147615789537]
  kdiff is a novel kernel-based measure for estimating distances between instances of structured data. It accounts for both self and cross similarities across the instances and is defined using a lower quantile of the distance distribution. Some theoretical results are provided for separability conditions using kdiff as a distance measure for clustering and classification problems.
  arXiv  Detail & Related papers  (2021-09-29T22:54:17Z)
• Manifold Hypothesis in Data Analysis: Double Geometrically-Probabilistic Approach to Manifold Dimension Estimation [92.81218653234669]
  We present new approach to manifold hypothesis checking and underlying manifold dimension estimation. Our geometrical method is a modification for sparse data of a well-known box-counting algorithm for Minkowski dimension calculation. Experiments on real datasets show that the suggested approach based on two methods combination is powerful and effective.
  arXiv  Detail & Related papers  (2021-07-08T15:35:54Z)
• Fast Approximation of the Sliced-Wasserstein Distance Using Concentration of Random Projections [19.987683989865708]
  The Sliced-Wasserstein distance (SW) is being increasingly used in machine learning applications. We propose a new perspective to approximate SW by making use of the concentration of measure phenomenon. Our method does not require sampling a number of random projections, and is therefore both accurate and easy to use compared to the usual Monte Carlo approximation.
  arXiv  Detail & Related papers  (2021-06-29T13:56:19Z)
• Instance-Optimal Compressed Sensing via Posterior Sampling [101.43899352984774]
  We show for Gaussian measurements and emphany prior distribution on the signal, that the posterior sampling estimator achieves near-optimal recovery guarantees. We implement the posterior sampling estimator for deep generative priors using Langevin dynamics, and empirically find that it produces accurate estimates with more diversity than MAP.
  arXiv  Detail & Related papers  (2021-06-21T22:51:56Z)
• Reweighting samples under covariate shift using a Wasserstein distance criterion [0.0]
  We study an optimal reweighting that minimizes the Wasserstein distance between the empirical measures of the two samples. The consistency and some convergence rates in terms of expected Wasserstein distance are derived. These results have some application in Uncertainty Quantification for decoupled estimation and in the bound of the generalization error for the Nearest Neighbor Regression.
  arXiv  Detail & Related papers  (2020-10-19T07:23:55Z)
• Minimax Optimal Estimation of KL Divergence for Continuous Distributions [56.29748742084386]
  Esting Kullback-Leibler divergence from identical and independently distributed samples is an important problem in various domains. One simple and effective estimator is based on the k nearest neighbor between these samples.
  arXiv  Detail & Related papers  (2020-02-26T16:37:37Z)

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.