PaperlayerView exact revision on arXiv

Source-linked AI summary

Finite Sample Bounds for Composite Hypothesis Testing

El{í}as Vera-Sig{ü}enza, Amedeo Roberto Esposito

arXiv:2608.28068v1cs.IT

TL;DR

The paper studies finite-sample composite binary testing with uniform Type I control and develops Rényi-based achievability and converse bounds. It identifies a KL-projection phase transition under exponentially decaying Type I error and gives exact exponents under compact convex finite-alphabet assumptions. A joint Rényi projection supplies a single uniformly controlling test without requiring finite-sample least favourability.

  • Problem

    Finite-sample bounds are missing for classical composite testing where one test uniformly controls Type I error over the null class while Type II error is evaluated over the alternative class.

  • Method

    The paper derives Rényi achievability and converse bounds, using a joint Rényi projection whose likelihood ratio controls both hypothesis classes uniformly.

  • Results

    For compact convex full-support classes on a finite alphabet, the bounds identify the phase transition and determine exact exponents on both sides, including the strong converse exponent.

  • Takeaways & Limitations

    The framework recovers the fixed-Type-I composite Chernoff–Stein exponent and provides a continuous connection between fixed and exponentially decaying Type I regimes.

Abstract

from arXiv · show

We investigate composite binary hypothesis testing in the finite sample regime under asymmetric error constraints. Using Rényi divergences, we derive explicit achievability and converse bounds for the optimal Type II error. When the Type I error is constrained to decay exponentially with sample size, the bounds identify a phase transition and yield a strong converse above it. In the composite problem, the phase transition threshold is given by the joint KL projection over the alternative and null classes. Achievability is obtained through a joint Rényi projection whose log likelihood ratio defines a single test with uniform error control over both hypothesis classes, without requiring the projected pair to be least favourable. For compact convex classes with full support on a finite alphabet, we determine the exact error exponents on both sides of the transition and show that the achievable exponent is attained at a unique Rényi order. The same framework recovers the fixed Type I composite Chernoff--Stein exponent and yields a polynomial refinement of the finite sample achievability result. We further identify conditions under which the projected pair is least favourable at finite sample size.

I. INTRODUCTION

The paper addresses finite-sample composite binary testing, where one test must control Type I error uniformly over the null class and Type II error over the alternative class. It develops explicit Rényi-based bounds, identifies the phase transition, and characterizes exact exponents under finite-alphabet assumptions.

  • Motivation: Composite testing requires a single test to handle unknown distributions in both the null and alternative classes.The Type I constraint must hold for every null distribution, while Type II error is assessed over the alternative class.
  • Prior approaches: Generalized likelihood-ratio and least-favourable-distribution approaches do not generally solve the composite problem without additional structure.Least favourability may fail to exist for general classes, and finite-sample least favourability is stronger than asymptotic exponent characterization.
  • Contribution: The paper fills a gap by providing finite-sample achievability and converse bounds for two composite hypotheses under uniform Type I control.The bounds address the classical setting in which Type II error is evaluated uniformly over the alternative class.
  • Main results: Under ε = e^-nr, the phase-transition threshold is the KL projection rc = infQ∈C1 infP∈C0 D(Q∥P).For r < rc, Type II error decays exponentially to zero; for r > rc, it converges exponentially to one.
  • Main results: For compact convex full-support classes on a finite alphabet, the paper determines exact exponents on both sides of the transition.The achievable exponent is the smallest exponent among simple pairs, while the converse-regime exponent is the largest strong converse exponent among simple pairs.
  • Further results: The Rényi framework recovers the fixed-Type-I composite Chernoff–Stein exponent and continuously connects it to the exponential-constraint regime as r ↓ 0.The order-zero and order-one limits connect the fixed and exponentially decaying Type I settings.
  • Further results: The authors also derive a polynomial refinement of finite-sample achievability and conditions yielding finite-sample least favourability.For separated one-parameter natural exponential families, the Rényi projection gives a least-favourable pair.

II. PROBLEM FORMULATION AND DEFINITIONS

The formulation treats null and alternative hypotheses as classes of probability laws and optimizes Type II error over randomized tests satisfying a uniform Type I constraint. The achievability construction uses a joint Rényi projection to obtain one likelihood-ratio test controlling both classes.

  • A. Problem formulation: The composite hypotheses are H_C0: X^n ∼ P^⊗n for some P ∈ C0 versus H_C1: X^n ∼ Q^⊗n for some Q ∈ C1.The classes contain nonempty families of probability laws on a common measurable space.
  • A. Problem formulation: A randomized test maps each observation to the probability of deciding the alternative.Randomization can attain an arbitrary prescribed finite-sample Type I level exactly.
  • A. Problem formulation: The optimal Type II error is the infimum over all randomized tests satisfying the uniform Type I constraint.The infimum is taken over tests admissible for the composite problem.
  • A. Converse bound: The finite-sample converse applies the simple-pair Rényi converse to every P ∈ C0 and Q ∈ C1, then optimizes over the classes and Rényi order.This produces a composite lower bound without assuming a least-favourable pair.
  • B. Achievability bound: Achievability requires one statistic whose exponential moments are uniformly controlled over both hypothesis classes.For a fixed pair, h = log(Q/P) has exponential moments equal to the Hellinger integral, linking the construction to Rényi divergence.
  • B. Achievability bound: The selected pair maximizes the Hellinger integral, equivalently minimizing Rényi divergence for λ ∈ (0, 1), and is called the joint Rényi projection.Convexity of the classes and concavity of the Hellinger integral yield the required uniform likelihood-ratio bounds.
  • B. Achievability bound: Theorem 2 gives a finite-sample achievability bound from a threshold test built from the joint Rényi projection.The result assumes common dominating measure, convexity, and weak compactness, but not finite-sample least favourability.

C. Phase transition under an exponential Type I constraint

With ε = e^-nr, the composite problem has a KL-projection phase transition: Type II error decays below the threshold and converges to one above it. Under compact convex full-support finite-alphabet assumptions, the corresponding exponents are exact.

  • Phase transition: For r > 0, the exponentially decaying Type I constraint is ε = e^-nr.The boundary case r = 0 is excluded from this formulation.
  • Phase transition: For r below D(C1∥C0), Type II error decays exponentially to zero; for r above it, Type II error converges exponentially to one.No assertion is made at r = D(C1∥C0).
  • Assumptions: The finite-alphabet assumptions ensure the support and order-one-limit conditions needed for the phase-transition theorem.Compactness and full support provide a common strictly positive lower bound over both classes.
  • Phase transition: The phase-transition threshold is D(C1∥C0), the joint KL projection from the alternative class onto the null class.The order-one limit identifies this threshold after controlling the order dependence of the Rényi projection.
  • Achievable regime: For compact convex classes with full support on a finite alphabet, the exact Type II exponent exists in the achievable regime.The projected test achieves the exponent for 0 < r < D(C1∥C0).
  • Achievable regime: The projected pair attains the smallest Type II exponent among all simple pairs and is least favourable at the exponent level.Minimax interchange and compactness establish coincidence between the composite and corresponding simple-pair exponents.
  • Achievable regime: The achievable exponent is attained at a unique Rényi order λ⋆ and is continuously differentiable in r.The order can be recovered directly from the derivative of the exponent.

B. Exact exponent in the converse regime

Above the threshold D(C1∥C0), the optimal Type II error converges to one, with an exactly characterized residual-probability exponent. Together with the achievable-regime result, this completes the exponent characterization across the phase transition.

  • Exact exponent in the converse regime: For r > D(C1∥C0), the optimal Type II error converges to one.Theorem 3 identifies this converse regime under the exponentially decaying Type I constraint.
  • Exact exponent in the converse regime: Theorem 5 establishes that the residual probability has an exact decay exponent for every r > D(C1∥C0).The finite-sample converse supplies an exponential upper bound, while Theorem 5 determines its exponent exactly.
  • Exact exponent in the converse regime: The achievable-regime Type II exponent is the smallest exponent among the corresponding simple binary problems.This result holds below the phase transition threshold.
  • Exact exponent in the converse regime: The converse-regime exponent for convergence of Type II error to one is the largest strong converse exponent among the simple pairs.Thus the two regimes are characterized through extremal exponents of simple binary problems.
  • Fixed Type I constraint and zero rate limit: The finite-sample achievability bound recovers the composite Chernoff–Stein exponent under a fixed Type I constraint.The fixed-Type-I regime corresponds to the order-zero boundary of the Rényi expression.
  • Fixed Type I constraint and zero rate limit: The threshold is D(C1∥C0), whereas a fixed Type I constraint yields the opposite KL direction, D(C0∥C1), for the Type II exponent.As r decreases to zero, the exponentially constrained achievable exponent converges to the fixed-Type-I exponent.

B. Polynomial refinement

The paper refines finite-sample achievability bounds with polynomial and logarithmic corrections, then characterizes when Rényi-projected pairs are also least favourable. Numerical illustrations show the bounds across achievable and converse regimes.

  • Polynomial refinement: An additional factor of order n^-1/2 appears in the sharper Type I error analysis, motivating a log n threshold correction and a polynomial Type II factor.The projected threshold initially leaves part of the available Type I error unused.
  • Polynomial refinement: Equation (17) determines the power of n but not the leading multiplicative constant; stronger constant-level conclusions require additional regularity conditions.This is an explicit limitation of the polynomial refinement under Proposition 2's assumptions.
  • Polynomial refinement: Corollary 4 shows that the polynomial power is determined directly by the slope of the exact Type II error exponent for 0 < r < D(C1∥C0).The result applies in the stated subcritical range.
  • Finite-sample least favourability: Rényi projection provides uniform exponential control over both classes, but that property alone does not imply finite-sample least favourability.The paper therefore asks which additional conditions make the projected pair attain the composite error probabilities.
  • Finite-sample least favourability: Under stochastic ordering conditions, the projected pair attains both composite error suprema for every projected threshold test, with exact reduction requiring optimality for the projected simple pair.These conditions hold for separated one-parameter natural exponential families.
  • Finite-sample least favourability: For separated one-parameter natural exponential families, the same endpoint pair is selected by every Rényi projection and is least favourable at every sample size.This connects the Rényi projection with an exact finite-sample reduction to the corresponding simple problem.

VIII. CONCLUSION

The paper develops finite-sample Rényi bounds for composite binary testing, identifies the exponential-error phase transition, and establishes exact exponents under compactness, convexity, and full support. Its projected likelihood-ratio test controls both classes uniformly without requiring finite-sample least favourability, while polynomial refinements expose remaining gaps.

  • VIII. CONCLUSION: Finite-sample Rényi achievability and converse bounds apply under a uniform Type I constraint, including exponentially decaying constraints ε = e^−nr.The bounds identify the phase transition for compact convex classes with full support on a finite alphabet.
  • VIII. CONCLUSION: Exact Type II error exponents hold on both sides of the phase transition, including a strong converse exponent above the threshold.The threshold is the joint KL projection over the alternative and null classes.
  • VIII. CONCLUSION: A joint Rényi projection yields one likelihood-ratio test with uniform error control over both classes without requiring the projected pair to be least favourable.Additional stochastic ordering conditions can make the projected pair least favourable and give an exact finite-sample reduction for separated one-parameter natural classes.
  • VIII. CONCLUSION: The Rényi framework recovers the fixed-Type-I composite Chernoff–Stein exponent and determines polynomial dependence on sample size at the selected order.The order-zero limit recovers the fixed-constraint exponent.
  • VIII. CONCLUSION: The polynomial refinement determines the power of n and logarithmic threshold correction but not the leading multiplicative constant.The tightened achievability bound currently requires numerical optimisation, and an analytical closed form remains open.
  • VIII. CONCLUSION: The converse applies the finite-sample Rényi converse to individual product-law pairs, leaving tighter optimisation over Bayesian mixture pairs open.The leading exponential rate is already exact under the stated compact finite-alphabet assumptions, so improvements concern finer finite-sample scales.

APPENDIX A BOUNDS

This appendix establishes finite-sample converse and achievability bounds using Rényi divergence, including their extension to composite classes. The achievability construction uses a joint Rényi projection and produces a uniformly admissible likelihood-ratio test.

  • APPENDIX A BOUNDS: For every admissible test and every null–alternative pair, Hölder’s inequality and Rényi additivity yield a finite-sample converse bound.The class-level bound follows by approximating the joint Rényi projection with pairs from the two classes.
  • APPENDIX A BOUNDS: The converse remains valid after taking the supremum over Rényi orders greater than one and the infimum over admissible tests.Infinite-divergence cases make the resulting bound trivial.
  • APPENDIX A BOUNDS: The achievability proof handles infinite likelihood-ratio values through moment assumptions and a product log-likelihood ratio.Independence, Markov’s inequality, and a calibrated threshold control the resulting error probabilities.
  • APPENDIX A BOUNDS: Weak compactness and continuity properties ensure that the Hellinger integral attains its maximum over the product of the density classes.Every maximising pair is therefore a joint Rényi projection.
  • APPENDIX A BOUNDS: The projected pair’s optimality and class convexity produce a likelihood-ratio test that is admissible with uniform control over both classes.The constant randomised test supplies the alternative bound with Type II error 1 − ε.
  • APPENDIX A BOUNDS: When ε = e−nr, the finite-sample bounds imply distinct achievable and converse regimes around the joint KL threshold.The proof uses Rényi orders approaching one and obtains a strictly positive exponent coefficient below the threshold.

G. Proof of Lemma 2

The proof establishes convergence of the joint Rényi threshold to the joint KL divergence and characterises the unique Rényi order governing the achievable exponent. Compactness, convexity, and full support provide the saddle-point and regularity properties needed for the result.

  • G. Proof of Lemma 2: Weak compactness and Rényi monotonicity imply limλ↑1 Dλ(C1∥C0) = D(C1∥C0).A nested-compactness contradiction argument rules out a strict gap between the limit and the KL projection.
  • G. Proof of Lemma 2: For 0 < r < D(Q∥P), a unique order sr ∈ (0, 1) satisfies D(Rsr∥P) = r and maximises the single-pair exponent.Type-class bounds provide the matching converse exponent after optimisation over orders.
  • G. Proof of Lemma 2: The type-class converse matches achievability asymptotically by taking n to infinity and the auxiliary order t upward to sr.This identifies the exact exponent for the single-pair problem in the achievable regime.
  • G. Proof of Lemma 2: The exponent admits equivalent variational forms through the tilted distribution identity and a saddle-point construction.Joint convexity, concavity, compactness, and continuity establish equality of the minimax values.

C. Proof of Corollary 1

This proof derives the composite achievable exponent using types, minimax interchange, and Rényi variational identities. Uniform full support and compact convexity yield convergence of finite-sample type expressions to the limiting exponent and establish the polynomial refinement.

  • C. Proof of Corollary 1: The type-based exponent is defined by minimising D(V∥Q) + a_r(V) over types and then maximising over Q ∈ C1.Uniform continuity and density of types imply convergence of the finite-sample exponent to its limiting counterpart.
  • C. Proof of Corollary 1: Type bounds show that the constructed test satisfies the uniform Type I constraint while attaining a polynomially corrected Type II lower bound.The admissibility argument uses D(V∥P) + a_r(V) ≥ r for every V and P ∈ C0.
  • C. Proof of Corollary 1: Symmetrising any admissible test reduces its analysis to constants on type classes, enabling an upper bound through the nearest null-class divergence dC0(V).Compactness supplies a null distribution attaining the infimum defining dC0(V).
  • C. Proof of Corollary 1: Compactness of C1 ensures that the supremum over alternative distributions is attained.This completes the limiting identification of the composite exponent.
  • C. Proof of Corollary 1: Sion’s minimax theorem converts the type optimisation into a Rényi variational expression over the composite classes.The perspective structure of relative entropy provides concavity in the auxiliary variables and convexity in V.
  • C. Proof of Corollary 1: The minimising distribution is proportional to Q(x)^λP(x)^(1−λ), and combining the variational identities proves the polynomially refined exponent.The resulting expression also yields the stated asymptotic form.

E. Proof of Lemma 3

The proof establishes finite-sample bounds by controlling bounded log-likelihood ratios and reducing composite errors to pairwise inequalities. It also characterizes threshold tests and derives uniform asymptotic estimates using Berry–Esseen arguments.

  • Taking the infimum over all pairs in C0 × C1 and letting λ ↓ 0 proves the stated bound.
  • Pairwise reduction and the Chernoff–Stein lemma yield the converse exponent D(C0∥C1).
  • When D(C0∥C1) = 0, a minimizing pair shares a common distribution R, and the constant test ϕn ≡ ε attains Type II error 1 − ε.
  • The threshold family is constructed by increasing boundary randomization across finitely many likelihood-ratio values until Type I error equals ε.
  • Along the threshold chain, Type I error increases while Type II error decreases, making the maximal admissible test the unique restricted minimizer.
  • For simple full-support hypotheses, the projected threshold family becomes the randomized likelihood-ratio family, whose maximal member is the randomized Neyman–Pearson test.
  • Uniform Berry–Esseen estimates apply over compact full-support classes because variances are uniformly bounded away from zero and centered third moments are uniformly controlled.

D. Proof of Proposition 2

The proposition’s proof analyzes the projected pair through tilted distributions and uniform concentration estimates. It then reduces composite endpoint errors to the corresponding simple endpoint pair using monotonicity and likelihood-ratio ordering.

  • The projected pair satisfies divergence identities involving r and 1 − λ, which locate the threshold between two asymptotic values.
  • The tilted classes remain compact with uniform full support, and the projected log-likelihood statistic is nonconstant, enabling uniform concentration estimates.
  • Choosing a logarithmic threshold shift controls Type I error exponentially while determining the corresponding threshold order for the Type II analysis.
  • Monotonicity of threshold tests and their miss functions, preserved under independent sums, yields the endpoint reductions for the composite problem.
  • Every composite-admissible test is admissible for the selected simple endpoint pair, while the projected endpoint test attains the simple endpoint error.

D. Proof of Proposition 4

The proof uses monotone likelihood-ratio structure to identify endpoint reductions and projected pairs, while the numerical appendix evaluates Rényi bounds by joint class optimization and outer order optimization.

  • D. Proof of Proposition 4: The Neyman–Pearson lemma and monotonicity show that endpoint tests are threshold tests in the statistic Tn, with the opposite tail handled by −T.
  • D. Proof of Proposition 4: When θC0 < θC1, divergence monotonicity identifies the projected pair through the interval endpoints; reversing the interval order reverses the derivative signs.
  • NUMERICAL EVALUATION OF THE BOUNDS: For affine classes, each Rényi order is evaluated by jointly optimizing the class parameters over [0, 1]2 before the outer optimization over λ.
  • NUMERICAL EVALUATION OF THE BOUNDS: For the first affine ternary example, the critical rate is rc = 0.094, with s⋆ = 0 and t⋆ = 0.639.
  • NUMERICAL EVALUATION OF THE BOUNDS: The displayed Rényi converse is the larger of the bound in Theorem 1 and the bound obtained from the opposite divergence direction.
  • NUMERICAL EVALUATION OF THE BOUNDS: The projected test is calibrated under the required Type I constraint, evaluated over the complete alternative class, and minimized across 27 candidate orders between 0.001 and 0.99.
Loading 2608.28068v1…