Related papers: Entropy Equivalence Testing

Entropy Equivalence Testing

URL: http://arxiv.org/abs/2605.23225v1
Date: Fri, 22 May 2026 04:35:04 GMT
Title: Entropy Equivalence Testing
Abstract summary: We introduce the problem of emphentropy equivalence testing for probability distributions.<n>We show that the optimal sample complexity for this task can be significantly lower than that of closeness testing.<n>We leverage this result to provide the first non-trivial testing algorithm for (standard) closeness of low-degree emphBayesian networks
Score: 43.089793195592115
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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.

Related papers

Near-optimal algorithms for private estimation and sequential testing of collision probability [1.62060928868899]
We describe an algorithm that satisfies $(alpha, beta)$-local differential privacy and estimates collision probability with error at most $epsilon$.<n>We also present a sequential testing algorithm for collision probability, which can distinguish between collision probability values that are separated by $epsilon$.
arXiv Detail & Related papers (2025-04-18T17:12:15Z)
Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
arXiv Detail & Related papers (2024-11-29T05:29:47Z)
Replicable Uniformity Testing [1.5883812630616523]
This work revisits uniformity testing under the framework of algorithmic replicability. We obtain a replicable tester using only $tildeO(sqrtn varepsilon-2 rho-1)$ samples.
arXiv Detail & Related papers (2024-10-12T02:55:17Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$. Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
arXiv Detail & Related papers (2023-06-28T16:33:39Z)
Near-Optimal Degree Testing for Bayes Nets [6.814860712547177]
We show that the sample of complexity of the problem is $tildeTheta (2n/2/varepsilon2)$. Our algorithm relies on a testing-by-learning framework, previously used to obtain sample-optimal testers.
arXiv Detail & Related papers (2023-04-13T03:48:31Z)
Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
We study the problem of high-dimensional sparse mean estimation in the presence of an $epsilon$-fraction of adversarial outliers. Our algorithms follow the Sum-of-Squares based, to algorithms approach.
arXiv Detail & Related papers (2022-06-07T16:49:54Z)
Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
We study the problem of testing discrete distributions with a focus on the high probability regime. We provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors.
arXiv Detail & Related papers (2020-09-14T16:09:17Z)
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
arXiv Detail & Related papers (2020-06-04T17:51:00Z)
Locally Private Hypothesis Selection [96.06118559817057]
We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
arXiv Detail & Related papers (2020-02-21T18:30:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.