Replicable Distribution Testing
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916824533172224 |
|---|---|
| author | Diakonikolas, Ilias Gao, Jingyi Kane, Daniel Liu, Sihan Ye, Christopher |
| author_facet | Diakonikolas, Ilias Gao, Jingyi Kane, Daniel Liu, Sihan Ye, Christopher |
| contents | We initiate a systematic investigation of distribution testing in the framework of algorithmic replicability. Specifically, given independent samples from a collection of probability distributions, the goal is to characterize the sample complexity of replicably testing natural properties of the underlying distributions. On the algorithmic front, we develop new replicable algorithms for testing closeness and independence of discrete distributions. On the lower bound front, we develop a new methodology for proving sample complexity lower bounds for replicable testing that may be of broader interest. As an application of our technique, we establish near-optimal sample complexity lower bounds for replicable uniformity testing -- answering an open question from prior work -- and closeness testing. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02814 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Replicable Distribution Testing Diakonikolas, Ilias Gao, Jingyi Kane, Daniel Liu, Sihan Ye, Christopher Machine Learning G.3 We initiate a systematic investigation of distribution testing in the framework of algorithmic replicability. Specifically, given independent samples from a collection of probability distributions, the goal is to characterize the sample complexity of replicably testing natural properties of the underlying distributions. On the algorithmic front, we develop new replicable algorithms for testing closeness and independence of discrete distributions. On the lower bound front, we develop a new methodology for proving sample complexity lower bounds for replicable testing that may be of broader interest. As an application of our technique, we establish near-optimal sample complexity lower bounds for replicable uniformity testing -- answering an open question from prior work -- and closeness testing. |
| title | Replicable Distribution Testing |
| topic | Machine Learning G.3 |
| url | https://arxiv.org/abs/2507.02814 |