Entropy Equivalence Testing
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
R\'enyi entropy, abundance distribution and the equivalence of ensembles
Distributions of abundances or frequencies play an important role in many fields of science, from biology to sociology, as does the R\'enyi entropy, which measures the diversity of a statistical ensemble. We derive a mat…
DiversitySociologyEquivalence Testing Under Privacy Constraints
Protecting individual privacy is essential across research domains, from socio-economic surveys to big-tech user data. This need is particularly acute in healthcare, where analyses often involve sensitive patient informa…
A Chasm Between Identity and Equivalence Testing with Conditional Queries
A recent model for property testing of probability distributions (Chakraborty et al., ITCS 2013, Canonne et al., SICOMP 2015) enables tremendous savings in the sample complexity of testing algorithms, by allowing them to…
Testing Autonomous Systems with Believed Equivalence Refinement
Continuous engineering of autonomous driving functions commonly requires deploying vehicles in road testing to obtain inputs that cause problematic decisions. Although the discovery leads to producing an improved system,…
Autonomous Driving