Finite-Sample Analysis of Elimination in Active Hypothesis Testing

• URL: http://arxiv.org/abs/2605.01039v1
• Date: Fri, 01 May 2026 19:08:12 GMT
• Title: Finite-Sample Analysis of Elimination in Active Hypothesis Testing
• Abstract summary: A fixed-confidence, finite-sample problem of active hypothesis testing arises in many safety-critical applications.<n>Situated in the context of sequential hypothesis testing, this paper studies the effect of hypothesis elimination on the stopping time.
• Score: 3.128335362695965
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fixed-confidence, finite-sample problem of active hypothesis testing arises in many safety-critical applications. Situated in the context of sequential hypothesis testing, this paper studies the effect of hypothesis elimination on the stopping time. We introduce an elimination-augmented Track-and-Stop algorithm, in which champion-specific active-opponent sets are progressively pruned, and sensing effort is reallocated toward the surviving alternatives. Our analysis derives a non-asymptotic upper bound on the expected stopping time. The gain in finite-sample from elimination appears on the scale of the non-leading term, resulting from tighter tracking and concentration constants on the reduced hypothesis set. Furthermore, we introduce an aggressiveness parameter to modulate the trade-off between faster elimination and weaker confidence guarantee. An experimental study on synthetic Gaussian instances confirms the theoretical predictions.

Related papers

• From Drift to Coherence: Stabilizing Beliefs in LLMs [23.20001878593831]
  Large language models (LLMs) are often hypothesized to perform implicit Bayesian inference.<n>Key coherence condition, the martingale property of predictive beliefs, has been shown to fail in controlled synthetic in-context learning settings.<n>We study belief dynamics induced by autoregressive answer resampling.
  arXiv  Detail & Related papers  (2026-06-16T12:01:26Z)
• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Towards Anytime-Valid Statistical Watermarking [63.02116925616554]
  We develop the first e-value-based watermarking framework, Anchored E-Watermarking, that unifies optimal sampling with anytime-valid inference.<n>Our framework can significantly enhance sample efficiency, reducing the average token budget required for detection by 13-15% relative to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2026-02-19T18:32:26Z)
• Predicting fixed-sample test decisions enables anytime-valid inference [0.3222802562733787]
  We introduce a simple procedure that transforms any fixed-sample hypothesis test into an anytime-valid test.<n>We ensure Type-I error control and near-optimal power with substantial sample savings when the null hypothesis is false.<n>In areas such as clinical trials, stopping early and safely can ensure that subjects receive the best treatments and accelerate the development of effective therapies.
  arXiv  Detail & Related papers  (2026-02-14T20:17:51Z)
• A Sample Efficient Conditional Independence Test in the Presence of Discretization [54.047334792855345]
  Conditional Independence (CI) tests directly to discretized data can lead to incorrect conclusions.<n>Recent advancements have sought to infer the correct CI relationship between the latent variables through binarizing observed data.<n>Motivated by this, this paper introduces a sample-efficient CI test that does not rely on the binarization process.
  arXiv  Detail & Related papers  (2025-06-10T12:41:26Z)
• Simulation-Based Inference for Adaptive Experiments [38.841210420855276]
  Multi-arm bandit experimental designs are increasingly being adopted over standard randomized trials.<n>We propose a simulation-based approach for conducting hypothesis tests and constructing confidence intervals for arm specific means.<n>Our results show that our approach achieves the desired coverage while reducing confidence interval widths by up to 50%, with drastic improvements for arms not targeted by the design.
  arXiv  Detail & Related papers  (2025-06-03T13:46:59Z)
• Prediction-Powered Causal Inferences [59.98498488132307]
  We focus on Prediction-Powered Causal Inferences (PPCI)<n>We first show that conditional calibration guarantees valid PPCI at population level.<n>We then introduce a sufficient representation constraint transferring validity across experiments.
  arXiv  Detail & Related papers  (2025-02-10T10:52:17Z)
• Uncertainty-Calibrated Test-Time Model Adaptation without Forgetting [65.21599711087538]
  Test-time adaptation (TTA) seeks to tackle potential distribution shifts between training and test data by adapting a given model w.r.t. any test sample.<n>Prior methods perform backpropagation for each test sample, resulting in unbearable optimization costs to many applications.<n>We propose an Efficient Anti-Forgetting Test-Time Adaptation (EATA) method which develops an active sample selection criterion to identify reliable and non-redundant samples.
  arXiv  Detail & Related papers  (2024-03-18T05:49:45Z)
• A unified Bayesian framework for interval hypothesis testing in clinical trials [4.911220423050305]
  The American Statistical Association (ASA) cautioned statisticians against making scientific decisions solely on the basis of traditional P-values. We demonstrate that the interval null hypothesis framework, when used in tandem with Bayes factor-based tests, is instrumental in circumnavigating the key issues of P-values.
  arXiv  Detail & Related papers  (2024-02-21T16:01:06Z)
• Semiparametric Efficient Inference in Adaptive Experiments [29.43493007296859]
  We consider the problem of efficient inference of the Average Treatment Effect in a sequential experiment where the policy governing the assignment of subjects to treatment or control can change over time. We first provide a central limit theorem for the Adaptive Augmented Inverse-Probability Weighted estimator, which is semi efficient, under weaker assumptions than those previously made in the literature. We then consider sequential inference setting, deriving both propensity and nonasymptotic confidence sequences that are considerably tighter than previous methods.
  arXiv  Detail & Related papers  (2023-11-30T06:25:06Z)
• Selective Nonparametric Regression via Testing [54.20569354303575]
  We develop an abstention procedure via testing the hypothesis on the value of the conditional variance at a given point. Unlike existing methods, the proposed one allows to account not only for the value of the variance itself but also for the uncertainty of the corresponding variance predictor.
  arXiv  Detail & Related papers  (2023-09-28T13:04:11Z)
• Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences with Possibly Dependent Observations [44.71254888821376]
  We provide the first type-I-error and expected-rejection-time guarantees under general non-data generating processes. We show how to apply our results to inference on parameters defined by estimating equations, such as average treatment effects.
  arXiv  Detail & Related papers  (2022-12-29T18:37:08Z)

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.