Power one sequential tests exist for weakly compact $\mathscr P$ against $\mathscr P^c$

• URL: http://arxiv.org/abs/2604.03218v1
• Date: Fri, 03 Apr 2026 17:45:42 GMT
• Title: Power one sequential tests exist for weakly compact $\mathscr P$ against $\mathscr P^c$
• Abstract summary: We show that there exists a level-$$ sequential test for any weakly compact $mathscr P$, that is power-one against $mathscr Pc$.<n>We show how to aggregate such tests into an $e$-process for $mathscr P$ that increases to infinity under $mathscr Pc$.
• Score: 38.54792440099341
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Suppose we observe data from a distribution $P$ and we wish to test the composite null hypothesis that $P\in\mathscr P$ against a composite alternative $P\in \mathscr Q\subseteq \mathscr P^c$. Herbert Robbins and coauthors pointed out around 1970 that, while no batch test can have a level $α\in(0,1)$ and power equal to one, sequential tests can be constructed with this fantastic property. Since then, and especially in the last decade, a plethora of sequential tests have been developed for a wide variety of settings. However, the literature has not yet provided a clean and general answer as to when such power-one sequential tests exist. This paper provides a remarkably general sufficient condition (that we also prove is not necessary). Focusing on i.i.d. laws in Polish spaces without any further restriction, we show that there exists a level-$α$ sequential test for any weakly compact $\mathscr P$, that is power-one against $\mathscr P^c$ (or any subset thereof). We show how to aggregate such tests into an $e$-process for $\mathscr P$ that increases to infinity under $\mathscr P^c$. We conclude by building an $e$-process that is asymptotically relatively growth rate optimal against $\mathscr P^c$, an extremely powerful result.

Related papers

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• An Optimal Analysis of the Product Test [42.29010058743949]
  Product testing decides whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition.<n>Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined.<n>As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from $mathsfQMA(k)$ to $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2026-07-23T16:17:44Z)
• The optimal betting wealth growth rate [38.54792440099341]
  This paper characterizes the best possible rate of growth of wealth in a Kelly betting game when repeatedly betting against a general i.i.d. null hypothesis $mathscrP$.<n>We show that it equals $lim_n to inftyn-1inf_P in (mathscr P)n)circcirc mathrmKL(Qn,P)$, where $mathscr Pn = Pn: P in mathscrP
  arXiv  Detail & Related papers  (2026-04-28T06:41:12Z)
• Optimal Anytime-Valid Tests for Composite Nulls [12.048034578791954]
  We consider the problem of designing optimal level-$$ power-one tests for composite nulls.<n>We first consider the finite-alphabet case($|mathcalX| = m infty$, and show that a test based on emphuniversal $e$-process(formed by the ratio of a universal predictor and the running null MLE) is optimal.
  arXiv  Detail & Related papers  (2025-12-23T04:14:56Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Non-iid hypothesis testing: from classical to quantum [4.258175645355975]
  We study hypothesis testing (aka state certification) in the non-identically distributed setting.<n>For any $d$-dimensional hypothesis state $sigma$, one can distinguish $rho_mathrmavg = sigma$ from $D_mathrmtr(rho_mathrmavg,sigma) > epsilon$ provided $T gg d/epsilon2$.
  arXiv  Detail & Related papers  (2025-10-07T17:19:26Z)
• Testing Closeness of Multivariate Distributions via Ramsey Theory [40.926523210945064]
  We investigate the statistical task of closeness (or equivalence) testing for multidimensional distributions. Specifically, given sample access to two unknown distributions $mathbf p, mathbf q$ on $mathbb Rd$, we want to distinguish between the case that $mathbf p=mathbf q$ versus $|mathbf p-mathbf q|_A_k > epsilon$. Our main result is the first closeness tester for this problem with em sub-learning sample complexity in any fixed dimension.
  arXiv  Detail & Related papers  (2023-11-22T04:34:09Z)
• Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
  We study the problem of detecting the correlation between two Gaussian databases $mathsfXinmathbbRntimes d$ and $mathsfYntimes d$, each composed of $n$ users with $d$ features. This problem is relevant in the analysis of social media, computational biology, etc.
  arXiv  Detail & Related papers  (2023-02-07T10:39:44Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  In high stake applications, active experimentation may be considered too risky and thus data are often collected passively. While in simple cases, such as in bandits, passive and active data collection are similarly effective, the price of passive sampling can be much higher when collecting data from a system with controlled states.
  arXiv  Detail & Related papers  (2021-06-18T07:54:23Z)
• 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)
• 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.

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