Optimistic Interior Point Methods for Sequential Hypothesis Testing by Betting
This work addresses a bottleneck in nonparametric sequential testing for researchers and practitioners, offering an incremental improvement over existing methods.
The paper tackles the problem of slow wealth accumulation in sequential hypothesis testing by betting, which delays null hypothesis rejection under the alternative. It introduces an interior-point method that avoids gradient explosion, enabling faster rejection while maintaining statistical guarantees and computational efficiency.
The technique of ``testing by betting" frames nonparametric sequential hypothesis testing as a multiple-round game, where a player bets on future observations that arrive in a streaming fashion, accumulates wealth that quantifies evidence against the null hypothesis, and rejects the null once the wealth exceeds a specified threshold while controlling the false positive error. Designing an online learning algorithm that achieves a small regret in the game can help rapidly accumulate the bettor's wealth, which in turn can shorten the time to reject the null hypothesis under the alternative $H_1$. However, many of the existing works employ the Online Newton Step (ONS) to update within a halved decision space to avoid a gradient explosion issue, which is potentially conservative for rapid wealth accumulation. In this paper, we introduce a novel strategy utilizing interior-point methods in optimization that allows updates across the entire interior of the decision space without the risk of gradient explosion. Our approach not only maintains strong statistical guarantees but also facilitates faster null hypothesis rejection, while being as computationally lightweight as ONS thanks to its closed-form updates.