@misc{jacobs_efficient_2025,
	title = {Efficient and {Stable} {Multi}-{Dimensional} {Kolmogorov}-{Smirnov} {Distance}},
	url = {http://arxiv.org/abs/2504.11299},
	doi = {10.48550/arXiv.2504.11299},
	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 Rd), 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 δ-precision two-sample hypothesis test using this distance. Finally, we show these metric and approximation properties do not hold for other popular variants.},
	language = {en},
	urldate = {2025-05-28},
	publisher = {arXiv},
	author = {Jacobs, Peter Matthew and Namjoo, Foad and Phillips, Jeff M.},
	month = apr,
	year = {2025},
	note = {arXiv:2504.11299 [stat]},
	keywords = {Computer Science - Computational Geometry, Computer Science - Machine Learning, Statistics - Computation},
}

{"_id":"2fM56yDkgKwYcPPmc","bibbaseid":"jacobs-namjoo-phillips-efficientandstablemultidimensionalkolmogorovsmirnovdistance-2025","author_short":["Jacobs, P. M.","Namjoo, F.","Phillips, J. M."],"bibdata":{"bibtype":"misc","type":"misc","title":"Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance","url":"http://arxiv.org/abs/2504.11299","doi":"10.48550/arXiv.2504.11299","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 Rd), 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 δ-precision two-sample hypothesis test using this distance. Finally, we show these metric and approximation properties do not hold for other popular variants.","language":"en","urldate":"2025-05-28","publisher":"arXiv","author":[{"propositions":[],"lastnames":["Jacobs"],"firstnames":["Peter","Matthew"],"suffixes":[]},{"propositions":[],"lastnames":["Namjoo"],"firstnames":["Foad"],"suffixes":[]},{"propositions":[],"lastnames":["Phillips"],"firstnames":["Jeff","M."],"suffixes":[]}],"month":"April","year":"2025","note":"arXiv:2504.11299 [stat]","keywords":"Computer Science - Computational Geometry, Computer Science - Machine Learning, Statistics - Computation","bibtex":"@misc{jacobs_efficient_2025,\n\ttitle = {Efficient and {Stable} {Multi}-{Dimensional} {Kolmogorov}-{Smirnov} {Distance}},\n\turl = {http://arxiv.org/abs/2504.11299},\n\tdoi = {10.48550/arXiv.2504.11299},\n\tabstract = {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 Rd), 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 δ-precision two-sample hypothesis test using this distance. Finally, we show these metric and approximation properties do not hold for other popular variants.},\n\tlanguage = {en},\n\turldate = {2025-05-28},\n\tpublisher = {arXiv},\n\tauthor = {Jacobs, Peter Matthew and Namjoo, Foad and Phillips, Jeff M.},\n\tmonth = apr,\n\tyear = {2025},\n\tnote = {arXiv:2504.11299 [stat]},\n\tkeywords = {Computer Science - Computational Geometry, Computer Science - Machine Learning, Statistics - Computation},\n}\n\n\n\n\n\n\n\n\n\n\n\n","author_short":["Jacobs, P. M.","Namjoo, F.","Phillips, J. M."],"key":"jacobs_efficient_2025","id":"jacobs_efficient_2025","bibbaseid":"jacobs-namjoo-phillips-efficientandstablemultidimensionalkolmogorovsmirnovdistance-2025","role":"author","urls":{"Paper":"http://arxiv.org/abs/2504.11299"},"keyword":["Computer Science - Computational Geometry","Computer Science - Machine Learning","Statistics - Computation"],"metadata":{"authorlinks":{}}},"bibtype":"misc","biburl":"https://bibbase.org/zotero-group/pratikmhatre/5933976","dataSources":["yJr5AAtJ5Sz3Q4WT4"],"keywords":["computer science - computational geometry","computer science - machine learning","statistics - computation"],"search_terms":["efficient","stable","multi","dimensional","kolmogorov","smirnov","distance","jacobs","namjoo","phillips"],"title":"Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance","year":2025}