Entropy Equivalence Testing
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914590850285568 |
|---|---|
| author | Canonne, Clément L. Pote, Yash Scarlett, Jonathan Yang, Joy Qiping |
| author_facet | Canonne, Clément L. Pote, Yash Scarlett, Jonathan Yang, Joy Qiping |
| contents | We introduce the problem of \emph{entropy equivalence testing} for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions $p,q$ and a parameter $\varepsilon \in(0,1/2]$, between $p=q$ and $|H(p)-H(q)| \geq \varepsilon$ (where $H$ denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree \emph{Bayesian networks}, which significantly improves on either the sample or time complexity of a baseline based on full learning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_23225 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Entropy Equivalence Testing Canonne, Clément L. Pote, Yash Scarlett, Jonathan Yang, Joy Qiping Data Structures and Algorithms Discrete Mathematics Information Theory Machine Learning Statistics Theory We introduce the problem of \emph{entropy equivalence testing} for probability distributions, a relaxation of the well-studied closeness testing problem, where the distribution testing algorithm is now only required to distinguish, given samples from two unknown distributions $p,q$ and a parameter $\varepsilon \in(0,1/2]$, between $p=q$ and $|H(p)-H(q)| \geq \varepsilon$ (where $H$ denotes the Shannon entropy). We provide a time- and sample-efficient algorithm for this task, showing that the optimal sample complexity for this task can be significantly lower than that of closeness testing. As an application, we leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree \emph{Bayesian networks}, which significantly improves on either the sample or time complexity of a baseline based on full learning. |
| title | Entropy Equivalence Testing |
| topic | Data Structures and Algorithms Discrete Mathematics Information Theory Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2605.23225 |