Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915244039733248 |
|---|---|
| author | Jacobs, Peter Matthew Namjoo, Foad Phillips, Jeff M. |
| author_facet | Jacobs, Peter Matthew Namjoo, Foad Phillips, Jeff M. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_11299 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance Jacobs, Peter Matthew Namjoo, Foad Phillips, Jeff M. Computation Computational Geometry Machine Learning 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. |
| title | Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance |
| topic | Computation Computational Geometry Machine Learning |
| url | https://arxiv.org/abs/2504.11299 |