Inverting Sequential Tests
March 29, 2023
\[\newcommand{\cX}{\mathcal{X}} \newcommand{\cP}{\mathcal{P}} \newcommand{\ind}{\mathbf{1}} \newcommand{\E}{\mathbb{E}} \newcommand{\cK}{\mathcal{K}}\]1. Fixed-time duality
There is a well known duality between fixed-time hypothesis testing and confidence intervals. Suppose we are testing the hypotheses
\[H_0: \theta = \theta^*, \quad H_1: \theta\neq \theta^*,\]for some fixed and known \(\theta^*\). We receive samples \(X^n \equiv X_1,\dots,X_n\), \(X_i\in \cX\) drawn from some distribution \(P\). A hypothesis test based on \(n\) samples is a function \(\phi: \cX^n \to \{0,1\},\) where we interpret \(\phi(X^n) = 1\) to mean “reject the null”, and \(\phi(X^n) = 0\) to mean “don’t reject the null” (or “maintain the null”, or “fail to reject the null”, etc. All are equivalent — no wonder Wittgenstein thought everything boiled down to language games). We say the test is level-\(\alpha\) if
\[\sup_{P\in H_0} P(\phi(X^n) = 1) \leq \alpha.\]That is, if the null is true, then \(\phi\) rejects it with probability at most \(\alpha\) . (In other words, the false positive rate is at most \(\alpha\).)
Meanwhile, a \((1-\alpha)\) confidence interval for \(\theta\) (or, more accurately, region) is a random set \(C = C(X^n)\) such that
\[\sup_{P\in\mathcal{P}(\theta)}P(\theta\in C(X^n)) \geq 1-\alpha,\]where \(\mathcal{P}(\theta)\) are all the distributions which have \(\theta\) as the parameter of interest. (E.g., if we are testing means, then it would be the set of all distributions with mean \(\theta\)).
Suppose we have a level-\(\alpha\) test \(\phi^{\theta^*}\) which tests the null \(H_0: \theta = \theta^*\) against the alternative \(H_1: \theta\neq \theta^*\). Construct the following confidence region:
\[C(X^n) = \{\theta: \phi^{\theta}(X^n) = 0\}.\]Then,
\[\sup_{P\in \mathcal{P}(\theta^*)}P(\theta^* \notin C(X^n)) = \sup_{P\in\cP(\theta^*)}P(\phi^{\theta^*}=1) =\sup_{P\in H_0}P(\phi^{\theta^*}=1) \leq \alpha,\]since the set of distributions in \(\cP(\theta^*)\) is the set for which the null \(H_0 : \theta =\theta^*\) is true. On the other hand, suppose you have a \((1-\alpha)\) confidence interval for some \(\theta^*\). Then construct a hypothesis test \(\phi\) which simply rejects if \(\theta^*\notin C(X_1,\dots,X_n)\). It’s easy to see that \(\phi\) is level-\(\alpha\). Therefore, confidence intervals are, in some sense, equivalent to confidence intervals. We’ll see that this equivalence extends to the sequential setting as well.
2. Sequential tests
A sequential test is a sequence of functions \(\phi = (\phi_t)_{t\geq 1}\) where \(\phi_t\) maps \(t\) observations \(Z_1,\dots,Z_t\) to \(\{0,1\}\). Similarly to fixed-time testing \(\phi_t = \phi_t(Z_1,\dots,Z_t)=1\) is interpreted as “reject the null” at which point, in the sequential setting, we stop testing. Thus, a sequential test can equivalently be identified by the stopping time \(\tau = \inf_t \{\phi_t = 1\}\). A sequential test is level-\(\alpha\) if
\[\sup_{P\in H_0} P(\exists t\geq 1: \phi_t=1) = \sup_{P\in H_0} P(\tau < \infty) \leq \alpha,\]meaning \(\phi\) controls the type I error simultaneously over all time steps.
As one would expect, the duality for sequential testing is based off of confidence sequences, which are confidence intervals that hold uniformly over time. More precisely, a confidence sequence for a parameter \(\theta\) is a random sequence of sets \(C = (C_t)_{t\geq 1}\) such that
\[\sup_{P\in \cP(\theta)} P(\forall t\geq 1: \theta \in C_t)\geq 1-\alpha.\]The duality between sequential tests and confidence sequences is nearly identical to the fixed-time setting. Given a \((1-\alpha)\)-confidence sequence \((C_t)\), defining \(\phi_t = \ind(\theta^* \notin C_t)\) gives a level-\(\alpha\) test. Likewise, if \(\phi = (\phi_t)\) is a level-\(\alpha\) sequential test then taking \(C_t = \{\theta: \phi_t^\theta = 0\}\) results in a \((1-\alpha)\) confidence sequence.
3. Constructing sequential tests
Noticing the duality between sequential tests and confidence sequences is all well and good – but does it help us when actually constructing sequential tests?
We’ve seen before how to construct confidence sequences using (super)martingales. We do this by employing Ville’s inequality. This relationship is a large part of the recent surge of interest in anytime-valid inference and game-theoretic probability. Indeed, the wealth process from the latter, which we recall is
\[\cK_t(\mu) = \prod_{i=1}^t (1 + \lambda_i (X_i - \mu)),\]is a \(P\)-martingale for any distribution \(P\) on \([0,1]^\infty\) with mean \(\mu\).
But notice we can generalize this further. Indeed, suppose \(E=(E_t)_{t\geq 1}\) is a sequence such that, for all \(P\in \cP\) there exists some (super)martingale \(M_t^P\) such that
\[E_t \leq M_t^P\quad P\text{-almost surely}.\]Then, the probability that \(E_t\) ever exceeds \(1/\alpha\) under any \(P\in \cP\) is also bounded by \(\alpha\). This immediately yields a sequential test for the null \(H_0: P \in \cP\) versus \(H_1: P\notin \cP\): set \(\tau = \inf_t \{ E_t > 1/\alpha\}\).
The construction is general enough that such processes have been given a name: e-processes. At any time \(t\) the value \(E_t\) of an e-process is an e-value for \(\cP\), which simply a random variable with expected value at most 1 under any \(P\in\cP\). This is because \(\E_P[E_t ]\leq \E_P[M_t^P]\leq 1\).
In fact, it has been shown that “well-behaved” e-processes must obey \(E_t = \inf_P M_t^P\). Therefore, if \(\cP = \{P\}\) is a singleton and \(M_t^P\) is a martingale (as opposed to a supermartingale), then
\[1 = \E_P [M_t^P] = \E_P [E_t] = \int E_t dP,\]which implies that \(E_t dP\) is the density of some distribution \(Q\). That is, \(dQ = E_t dP\), so \(E_t\) is the Radon-Nikodym derivative \(dQ / dP\). Thus, in this case, we have simply recovered the likelihood ratio-test (based on the samples \(X_1,\dots,X_t\))! In fact, this shows that the likelihood-ratio test is anytime-valid. But the theory of e-processes is more general than this, since we may consider composite distributions \(\cP\) (such as, e.g., the set of all bounded distibutions with a common mean).
The moral of the story is: If we can find an e-process for \(\cP\), then we have a sequential test for \(H_0: P\in \cP\), \(H_1:P\notin \cP\). And finding e-processes is made easier via various tools from sequential analysis: martingales, Ville’s inequality, and game-theoretic probability.
