Algorithms and Hardness for Estimating Statistical Similarity
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_ | 1866916771235102720 |
|---|---|
| author | Bhattacharyya, Arnab Gayen, Sutanu Meel, Kuldeep S. Myrisiotis, Dimitrios Pavan, A. Vinodchandran, N. V. |
| author_facet | Bhattacharyya, Arnab Gayen, Sutanu Meel, Kuldeep S. Myrisiotis, Dimitrios Pavan, A. Vinodchandran, N. V. |
| contents | We introduce and study the computational problem of determining statistical similarity between probability distributions. For distributions $P$ and $Q$ over a finite sample space, their statistical similarity is defined as $S_{\mathrm{stat}}(P, Q) := \sum_x \min(P(x), Q(x))$. Despite its fundamental nature as a measure of similarity between distributions, capturing essential concepts such as Bayes error in prediction and hypothesis testing, this computational problem has not been previously explored. Recent work on computing statistical distance has established that, somewhat surprisingly, even for the simple class of product distributions, exactly computing statistical similarity is $\#\mathsf{P}$-hard. This motivates the question of designing approximation algorithms for statistical similarity. Our first contribution is a Fully Polynomial-Time deterministic Approximation Scheme (FPTAS) for estimating statistical similarity between two product distributions. Furthermore, we also establish a complementary hardness result. In particular, we show that it is $\mathsf{NP}$-hard to estimate statistical similarity when $P$ and $Q$ are Bayes net distributions of in-degree $2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_10527 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithms and Hardness for Estimating Statistical Similarity Bhattacharyya, Arnab Gayen, Sutanu Meel, Kuldeep S. Myrisiotis, Dimitrios Pavan, A. Vinodchandran, N. V. Data Structures and Algorithms Computational Complexity We introduce and study the computational problem of determining statistical similarity between probability distributions. For distributions $P$ and $Q$ over a finite sample space, their statistical similarity is defined as $S_{\mathrm{stat}}(P, Q) := \sum_x \min(P(x), Q(x))$. Despite its fundamental nature as a measure of similarity between distributions, capturing essential concepts such as Bayes error in prediction and hypothesis testing, this computational problem has not been previously explored. Recent work on computing statistical distance has established that, somewhat surprisingly, even for the simple class of product distributions, exactly computing statistical similarity is $\#\mathsf{P}$-hard. This motivates the question of designing approximation algorithms for statistical similarity. Our first contribution is a Fully Polynomial-Time deterministic Approximation Scheme (FPTAS) for estimating statistical similarity between two product distributions. Furthermore, we also establish a complementary hardness result. In particular, we show that it is $\mathsf{NP}$-hard to estimate statistical similarity when $P$ and $Q$ are Bayes net distributions of in-degree $2$. |
| title | Algorithms and Hardness for Estimating Statistical Similarity |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2502.10527 |