A doubly composite Chernoff-Stein lemma and its applications

• URL: http://arxiv.org/abs/2510.06342v1
• Date: Tue, 07 Oct 2025 18:06:30 GMT
• Title: A doubly composite Chernoff-Stein lemma and its applications
• Authors: Ludovico Lami,
• Abstract summary: Given a sequence of random variables, discriminating between two hypotheses on the underlying probability distribution is a key task in statistics and information theory.<n>Generalisations of this result exist in the case of composite hypotheses, but mostly to settings where the probability distribution of $Xn$ is not genuinely correlated.<n>Here, we establish a general Chernoff-Stein lemma that applies to the setting where both hypotheses are composite and genuinely correlated.
• Score: 13.283296551055734
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a sequence of random variables $X^n=X_1,\ldots, X_n$, discriminating between two hypotheses on the underlying probability distribution is a key task in statistics and information theory. Of interest here is the Stein exponent, i.e. the largest rate of decay (in $n$) of the type II error probability for a vanishingly small type I error probability. When the hypotheses are simple and i.i.d., the Chernoff-Stein lemma states that this is given by the relative entropy between the single-copy probability distributions. Generalisations of this result exist in the case of composite hypotheses, but mostly to settings where the probability distribution of $X^n$ is not genuinely correlated, but rather, e.g., a convex combination of product distributions with components taken from a base set. Here, we establish a general Chernoff-Stein lemma that applies to the setting where both hypotheses are composite and genuinely correlated, satisfying only generic assumptions such as convexity (on both hypotheses) and some weak form of permutational symmetry (on either hypothesis). Our result, which strictly subsumes most prior work, is proved using a refinement of the blurring technique developed in the context of the generalised quantum Stein's lemma [Lami, IEEE Trans. Inf. Theory 2025]. In this refined form, blurring is applied symbol by symbol, which makes it both stronger and applicable also in the absence of permutational symmetry. The second part of the work is devoted to applications: we provide a single-letter formula for the Stein exponent characterising the discrimination of broad families of null hypotheses vs a composite i.i.d. or an arbitrarily varying alternative hypothesis, and establish a 'constrained de Finetti reduction' statement that covers a wide family of convex constraints. Applications to quantum hypothesis testing are explored in a related paper [Lami, arXiv:today].

Related papers

• Generalised quantum Sanov theorem revisited [13.283296551055734]
  Given two families of quantum states $A$ and $B$, quantum hypothesis testing is the task of determining whether an unknown quantum state belongs to $A$ or $B$.<n>In quantum Shannon theory, a fundamental role is played by the Stein exponent, i.e. the rate of decay of the type II error probability for a given threshold on the type I error probability.<n>In this work, we establish a general formula for the Stein exponent where both hypotheses are allowed to be composite.
  arXiv  Detail & Related papers  (2025-10-07T18:05:25Z)
• The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints [7.10734752120062]
  We show that sequential interaction does not help reduce the sample complexity of distributed simple binary hypothesis testing.<n>The second problem suggests tightening existing sample complexity bounds for communication-constrained simple binary hypothesis testing.
  arXiv  Detail & Related papers  (2025-06-16T16:50:27Z)
• Score-based generative models are provably robust: an uncertainty quantification perspective [4.396860522241307]
  We show that score-based generative models (SGMs) are provably robust to the multiple sources of error in practical implementation. Our primary tool is the Wasserstein uncertainty propagation (WUP) theorem. We show how errors due to (a) finite sample approximation, (b) early stopping, (c) score-matching objective choice, (d) score function parametrization, and (e) reference distribution choice, impact the quality of the generative model.
  arXiv  Detail & Related papers  (2024-05-24T17:50:17Z)
• Generalized Stein's lemma and asymptotic equipartition property for subalgebra entropies [12.294224442885891]
  We show that the assertion of the generalized quantum Stein's lemma is true for the setting where the second hypothesis is the state space of any subalgebra $mathcalN$. As an application in resource theory, we show that the relative entropy of a subalgebra is the dilution cost under suitable operations.
  arXiv  Detail & Related papers  (2024-01-05T23:46:53Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  We develop a suite of non-asymptotic theory towards understanding the data generation process of diffusion models. In contrast to prior works, our theory is developed based on an elementary yet versatile non-asymptotic approach.
  arXiv  Detail & Related papers  (2023-06-15T16:30:08Z)
• Statistical Properties of the Entropy from Ordinal Patterns [55.551675080361335]
  Knowing the joint distribution of the pair Entropy-Statistical Complexity for a large class of time series models would allow statistical tests that are unavailable to date. We characterize the distribution of the empirical Shannon's Entropy for any model under which the true normalized Entropy is neither zero nor one. We present a bilateral test that verifies if there is enough evidence to reject the hypothesis that two signals produce ordinal patterns with the same Shannon's Entropy.
  arXiv  Detail & Related papers  (2022-09-15T23:55:58Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  We propose a weaker assumption that we call $2$-adjacency faithfulness. We propose a sound orientation rule for causal discovery that applies under weaker assumptions.
  arXiv  Detail & Related papers  (2020-10-27T13:04:08Z)
• Asymptotic relative submajorization of multiple-state boxes [0.0]
  Pairs of states are the basic objects in the resource theory of asymmetric distinguishability (Wang and Wilde, 2019), where free operations are arbitrary quantum channels that are applied to both states. We consider boxes of a fixed finite number of states and study an extension of the relative submajorization preorder to such objects. This preorder characterizes error probabilities in the case of testing a composite null hypothesis against a simple alternative hypothesis, as well as certain error probabilities in state discrimination.
  arXiv  Detail & Related papers  (2020-07-22T08:29:52Z)
• Contextuality scenarios arising from networks of stochastic processes [68.8204255655161]
  An empirical model is said contextual if its distributions cannot be obtained marginalizing a joint distribution over X. We present a different and classical source of contextual empirical models: the interaction among many processes. The statistical behavior of the network in the long run makes the empirical model generically contextual and even strongly contextual.
  arXiv  Detail & Related papers  (2020-06-22T16:57:52Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.